leetcode 907. Sum of Subarray Minimums | 907. 子数组的最小值之和（单调栈）

https://leetcode.com/problems/sum-of-subarray-minimums/

单调栈问题。参考左神算法课：https://ke.qq.com/webcourse/3067253/103187834#taid=10646309101817205&vid=5285890813430715450

相当于找当前元素属于哪些子序列的最小值，如下图，以 10 位置的 7 为例，它可以是以下标 6~10 任意一个作为开始，到下标 10~14 任意一个作为结束的所有 5*5=25 个子数组的最小值，所以，以 7 为最小值的 subarray sum = 5*5*7。

需要注意的是出现相等数字时候的情况，具体表现为当遇到相等数字时，不重复计算即可。可以听左神讲的，也可以自己画一下，试一下就懂了。

class Solution {
    public static final int MOD = (int) (Math.pow(10, 9) + 7);

    public int sumSubarrayMins(int[] arr) {
        int L = arr.length;
        // 找左边第一个【小于等于】h[i]的数
        // 从右向左遍历，维护单调增栈，小/等数h[i]不断将大数h[j]弹出，则h[i]左边第一个小于h[i]的数为h[j]
        Stack valueStack = new Stack<>();
        Stack indexStack = new Stack<>();
        int[] leftIndex = new int[L]; // i左边第一个小于i的数的下标
        Arrays.fill(leftIndex, -1);
        for (int i = L - 1; i >= 0; i--) {
            while (!valueStack.isEmpty() && valueStack.peek() >= arr[i]) {
                leftIndex[indexStack.pop()] = i;
                valueStack.pop();
            }
            valueStack.push(arr[i]);
            indexStack.push(i);
        }
        // 找右边第一个【小于】h[i]的数
        // 从左向右遍历，维护单调不减栈
        valueStack = new Stack<>();
        indexStack = new Stack<>();
        int[] rightIndex = new int[L]; // i右边第一个小于i的数的下标
        Arrays.fill(rightIndex, L);
        for (int i = 0; i < L; i++) {
            while (!valueStack.isEmpty() && valueStack.peek() > arr[i]) {
                rightIndex[indexStack.pop()] = i;
                valueStack.pop();
            }
            valueStack.push(arr[i]);
            indexStack.push(i);
        }

        long result = 0;
        for (int i = 0; i < L; i++) {
            int fromRange = i - leftIndex[i];
            int toRange = rightIndex[i] - i;
            result += (long)fromRange * toRange * arr[i];
            result %= MOD;
        }
        return (int) result;
    }
}