单调栈练习（一）— 子数组区间内最小值问题

题目
给定一个只包含正数的数组arr，arr中任何一个子数组sub，
一定都可以算出(sub累加和 ) * (sub中的最小值)是什么，
那么所有子数组中，这个值最大是多少？

前置知识-单调栈结构
暴力解
这道题暴力解的思路是，遍历数组 0 ~ 0、0 ~ 1 … 0 ~ N - 1 ， 1 - 1、1 - 2… 1 - N - 1 一直到N - 1 ~ N - 1，每一个范围内求出最小值和子数组的累加和，相乘后，取最大值。数组长度是N，三层循环，时间复杂度$O(N^3)$。

代码

 public static int max2(int[] arr) {
        Integer maxNum = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                Integer minNum = Integer.MAX_VALUE;
                int sum = 0;
                //从 i ~ j 范围子数组求累加和和最小值
                for (int k = i; k <= j; k++) {
                    sum += arr[k];
                    minNum = Math.min(minNum, arr[k]);
                }
                //相乘取最大值作比较
                maxNum = Math.max(maxNum, minNum * sum);
            }
        }
        return maxNum;
    }

暴力解的方式没什么好说的，下面来看看用单调栈结构解答这道题，时间复杂度$O(N)$。

单调栈
单调栈结构首先求前缀和数组。并且维护一个从栈底到栈顶有小到大的单调栈结构。
preSum[0]= arr[0]
preSum[1] = arr[0] + arr[1]
preSum[2] = arr[0] + arr[1] + arr[2]
preSum[3] = arr[0] + arr[1] + arr[2] + arr[3]

生成前缀和数组后，数组进行 0 ~ N - 1范围内遍历，并且在遍历过程中进行判断。
当前来到了 i 位置，并且栈顶元素 >= arr[i]数组 i 位置的值 。则弹出栈顶元素（作为当前子数组区间内的最小值）。
因为是 arr[i] 位置比栈顶元素小，使我弹出，所以是我当前弹出栈顶元素的右侧最近且小的值，那左侧最近且小的值呢？ 弹出当前元素后栈中的栈顶元素。

所以如果弹出后栈不为null的话，则使用preSum[ i - 1] - preSum[stack.peek()] （preSum[i - 1]是子数组左边界， preSum[stack.peek()是子数组的右边界），就可以求出子数组范围的前缀和， * 当前弹出的元素，即为子数组区间范围内的最小值。
如果当前元素出栈后，栈中为null，没有其他元素，则说明当前 arr[i] 位置就是数组 0 ~ i 范围内最小值，直接去preSum[i - 1]的累加和 * 当前弹出的元素 即可。

如果上面循环跑完，栈中还有其他元素，则说明此时栈顶元素一定是 arr中的N - 1位置，直接循环全部弹出栈，并判断弹出后栈中是否为null。
此时栈中剩余元素均代表数组中右侧没有最近且小于当前栈顶元素的值，左侧最近且小于当前栈顶元素的值，看弹出后的栈顶元素，取前缀和数组相减即可。

代码

 public static int max1(int[] arr) {
        int N = arr.length;
        int[] preSum = new int[N];
        preSum[0] = arr[0];
        for (int i = 1; i < N; i++) {
            preSum[i] += preSum[i - 1] + arr[i];
        }
        //单调栈结构
        Stack<Integer> stack = new Stack<>();
        Integer max = Integer.MIN_VALUE;
        for (int j = 0; j < N; j++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[j]) {
                
                Integer cur = stack.pop();
                //preSum[j - 1]：当前arr[j]位置值，比栈顶cur元素小，是cur出栈，所以子数组右边界就取到 j - 1位置
                //如果栈中还有元素，说明弹出后的当前栈顶元素，就是左侧最近且小的，作为子数组范围左边界
                //这样就可以确定当前弹出的栈顶元素 cur 为子数组中最小值。
                max = Math.max(max, (stack.isEmpty() ? preSum[j - 1] : preSum[j - 1] - preSum[stack.peek()]) * arr[cur]);
            }
            stack.push(j);
        }

        while (!stack.isEmpty()) {
            Integer cur = stack.pop();
            max = Math.max(max, (stack.isEmpty() ? preSum[N - 1] : preSum[N - 1] - preSum[stack.peek()]) * arr[cur]);
        }
        return max;
    }

上面虽然很多循环，但是数组只 从 0 ~ N - 1位置走了一遍，其余都是进栈出栈的操作，所以时间复杂度很低。

对数器
随机生成数组并大数据大样本量进行测试，并用暴力解和单调栈进行对比。

public static int[] generateRandomArray(int maxLength, int maxValue) {
        int[] arr = new int[(int) (Math.random() * maxLength) + 20];
        for (int i = 0; i < arr.length; i++) {
            int value = (int) (Math.random() * maxValue) + 20;
            arr[i] = value;
        }
        return arr;
    }

    public static void main(String[] args) {
        int maxLength = 20;
        int maxValue = 20;
        int test = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < test; i++) {
            int[] arr = generateRandomArray(maxLength, maxValue);
            int ans1 = max1(arr);
            int ans2 = max2(arr);
            if (ans1 != ans2){
                System.out.println("GG !!!!!!");
                System.out.println("ans1 : " + ans1);
                System.out.println("ans2 : " + ans2);
                System.out.println();
                for (int num : arr){
                    System.out.print(num +" " );
                }
                System.out.println();
                break;
            }
        }
        System.out.println("测试结束");
    }