14. 单调栈结构

单调栈是栈数据结构的一种变形，在满足栈基本特性先进后出（FILO）的条件下，还要满足栈内元素遵循单调性。比如从栈底到栈顶元素保持递增的称之为单调递增栈，从栈底到栈顶元素保持递减的栈称之为单调递减栈。

单调递增栈，通过峰底剔除峰谷
单调递减栈，通过峰谷剔除峰

技巧：使用数组模拟栈结构能够大大提升常数时间复杂度。

注：
单调栈出入栈过程中，只有右侧可以实现严格最近小于或者小于等于的条件，如果求左侧最近满足的条件需要通过右侧进行等价转换。
即对于数据中的重复值，在不使用链表的情况下，可以找到每个数右侧满足的情况，但是左侧是不满足的，所有需要通过反转，等价转换。
（1）求当前数右侧第一个比它小的或者小于等于它的数的位置，可以通过修改出栈条件,<或者<=来实现
（2）求当前数左侧第一个比它小的或者小于等于它的数据位置，通过对原始数据进行反转，然后求原始数据最左侧小于或者小于等于它的数，即求反转数据的右侧第一个小于等于它的数。

题目1：
https://leetcode-cn.com/problems/sum-of-subarray-minimums/

给定一个数组arr，返回所有 子数组最小值 的累加和
测试链接：https://leetcode-cn.com/problems/sum-of-subarray-minimums/
// subArrayMinSum1是暴力解
// subArrayMinSum2是最优解的思路
// sumSubarrayMins是最优解思路下的单调栈优化
// Leetcode上只提交sumSubarrayMins方法，时间复杂度O(N)，可以直接通过
在不重复的情况下:
必须以x作为最小值的子数组的个数m m*x
分别计算以每个数组值作为最小值的子数组的个数，当前计算个数乘以当前计算的最小值，然后相加得到最后的累加和。
在数组元素重复的情况下就不可以按照上述方法进行了
2 4 5 3 6 6 6 3 7 8 6 3 5 3 2
加入以第一个3作为最小值的时候，统计的时候不能超过第二个3，防止重复统计。以第二个3作为最小值的时候左边依然从4开始统计，右侧不能到达第三个3的位置。

public static int sumSubarrayMins(int[] arr) {
        int[] left = nearLessEqualLeft(arr);
        int[] right = nearLessRight(arr);
        long ans = 0;
        for (int i = 0; i < arr.length; i++) {
            long start = i - left[i];  //  i - (left[i]+1) + 1
            long end = right[i] - i;   //  right[i]  - (i+1) + 1
            ans += start * end * (long) arr[i];
            ans %= 1000000007;
        }
        return (int) ans;
    }
    // 获取左侧最近的小于等于当前数的位置。通过反转数组，求反转后的右侧满足条件的的即原始数组左侧的满足条件的。
    public static int[] nearLessEqualLeft(int[] arr) {
        int N = arr.length;
        int[] left = new int[N];
        Stack<Integer> stack = new Stack<>();
        for (int i = N - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) {
                left[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            left[stack.pop()] = -1;
        }
        return left;
    }
    // 获取右侧最近的严格小于当前数的位置
    public static int[] nearLessRight(int[] arr) {
        int N = arr.length;
        int[] right = new int[N];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                right[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            right[stack.pop()] = N;
        }
        return right;
    }