单调栈

单调栈是什么？

单调栈就是一个栈结构，里面存放的内容从上到下是依次递增或者递减的。它可以用来解决在一个数组中找出每个元素对应左右两部分比自己小的值并且最近的值的情况。并且保证时间复杂度在O(n)

思想是什么？

给定一个数组，在遍历数组的过程中，我想把数组中元素对应的索引放入到单调栈中，怎么放呢？我们来捋下思路：

在数组中不出现重复数字的时候：

遍历到当前元素的时候，判断单调栈是否为空，如果为空，就将元素放入到单调栈中。如果不为空，需要判断栈顶元素和当前元素的大小，如果栈顶元素比当前元素大，那么就需要将栈顶元素弹出，在弹出的后，就可以处理栈顶元素对应的左右比自己小的值并且最近的信息了。

在数组中出现重复数字的时候：

与上面不同的是，这种情况需要加个链表，也就是说，我们的单调栈不再是简单的保存一下索引值了，而是将相等的索引放入到一个链表中，然后将链表压入到栈中。

代码咋实现的？

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * Author:markusZhang
 * Date:Create in 2020/7/29 21:01
 * todo: 单调栈
 */
public class MonotonousStack {
    /**
     * 在数组中想找到一个数，左边和右边比这个数小、且离这个数最近的位置
     * 如果对每一个数都想求到这样的信息，能不能整体代价达到O(n)?需要使用到单调栈结构
     * 单调栈结构的原理和实现
     */
    public static int[][] process_repeatable(int []arr){
        if (arr == null || arr.length<=0){
            return null;
        }
        //单调栈里面的元素放的一定是从下到上依次递减的元素。
        Stack<List<Integer>> mStack = new Stack<>();
        //它存放的是需要返回的信息，行对应索引，列对应该索引对应的值左右对应最近的比自己小的值
        int res[][] = new int[arr.length][2];
        for (int i=0;i<arr.length;i++){
            //栈不为空，并且栈顶元素大于当前遍历的元素时处理的操作
            while(!mStack.isEmpty() && arr[mStack.peek().get(0)] > arr[i]){
                //我现在需要处理当前栈顶元素的左右比自己小的值
                List<Integer> popIndex = mStack.pop();
                for (Integer index : popIndex) {
                    res[index][0] = mStack.isEmpty()?-1:mStack.peek().get(mStack.peek().size()-1);
                    res[index][1] = i;
                }
            }
            //这一步就是判断当前栈顶链表中的索引对应的数组值是否与当前对应的值相等
            if (!mStack.isEmpty() && arr[mStack.peek().get(0)] == arr[i]){
                mStack.peek().add(i);
            }else{
                //其他情况，就新生成一个链表然后压入到栈中
                List<Integer> list = new ArrayList<>();
                list.add(i);
                mStack.push(list);
            }
        }
        while(!mStack.isEmpty()){
            List<Integer> pop = mStack.pop();
            for (Integer integer : pop) {
                int popIndex = pop.get(pop.size()-1);
                res[integer][0] = mStack.isEmpty()?-1:mStack.peek().get(mStack.peek().size()-1);
                res[integer][1] = -1;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int arr[] = {1,2,3,1,4,5,4,6};
        int[][] ints = process_repeatable(arr);
        for (int i = 0; i < ints.length;i++){
            System.out.print(i+"左部对应比自己小的值最近的元素索引："+ints[i][0]+"\t");
            System.out.println(i+"右部对应比自己小的值最近的元素索引："+ints[i][1]);
        }
    }
}

情景应用

定义：数组中累积和与最小值的乘积，假设叫做指标A。给定一个数组，请返回数组中，指标A最大的值。

给定一个数组，里面会有很多子数组，我现在想要得到众多子数组中的得到指标的最大值

这道题我们可以这样规定，在遍历数组的时候，遍历到每个元素的时候就将当前元素当作最小值组成的子数组然后求指标。

那我们可以将单调栈应用到这个场景当中，我每次求的当前元素的左边比自己小的且离自己最近的数的索引记录一下，然后将右边比自己小的且离自己最近的数的索引记录一下，那么在这两个索引之间组成的子数组的就是以当前元素为最小值。那么我们对每个数组对应的这样的子数组都求一下指标，那么整体返回数组的指标的最大值肯定在这其中。

我们来编写代码实现一下：

public static int maxZhiBiao(int []arr){
    if (arr == null || arr.length == 0){
        return -1;
    }
    Stack<List<Integer>> mStack = new Stack<>();
    int [][]res = new int[arr.length][2];
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        while(!mStack.isEmpty() && arr[mStack.peek().get(0)] > arr[i]){
            List<Integer> popIndex = mStack.pop();
            for (Integer index : popIndex) {
                res[index][0] = mStack.isEmpty()?-1:mStack.peek().get(mStack.peek().size()-1);
                res[index][1] = i;
                int calculatorZhiBiao = calculatorZhiBiao(arr, res[index][0], res[index][1], index);
                max = max>calculatorZhiBiao?max:calculatorZhiBiao;
                //System.out.println(max);
            }
        }
        if (!mStack.isEmpty() && arr[mStack.peek().get(0)] == arr[i]){
            mStack.peek().add(i);
        }else{
            List<Integer> list = new ArrayList<>();
            list.add(i);
            mStack.push(list);
        }
    }
    while(!mStack.isEmpty()){
        List<Integer> pop = mStack.pop();
        for (Integer integer : pop) {
            int popIndex = pop.get(pop.size()-1);
            res[integer][0] = mStack.isEmpty()?-1:mStack.peek().get(mStack.peek().size()-1);
            res[integer][1] = -1;
            int calculatorZhiBiao = calculatorZhiBiao(arr, res[integer][0], res[integer][1], integer);
            max = max>calculatorZhiBiao?max:calculatorZhiBiao;
            //System.out.println(max);
        }
    }
    return max;
}
private static int calculatorZhiBiao(int []arr,int i,int j,int index){
    int value = 0;
    int sum = 0;
    j = j==-1?arr.length:j;
    for (int m=i+1;m<j;m++){
        sum += arr[m];
    }
    value = arr[index] * sum;
    return value;
}