907 Sum of Subarray Minimums

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

要看出来用单调栈很不容易啊，关键还是转化问题到求每个val为最小值的subarray有几个，这样就转化到84了

class Solution {
    // 0   1  2     3 4
    // s.p    idx     i
    // 本质上是要知道以每个val为最小值的subarray有多少个
    public int sumSubarrayMins(int[] array) {
        long mod = 1000000007;
        long sum = 0;
        int n = array.length;
        int[] arr = new int[n+2];
    //找左右更小值,或者要保证在区间中最小，用max stack, 遇到小值pop，所以左右需要有假的小值
        for (int i = 0; i < n; i++) {
            arr[i+1] = array[i];
        }
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (int i = 1; i <= n + 1; i++) {
            if (arr[stack.peek()] <= arr[i]) {
                stack.push(i);
            } else {
                while (arr[stack.peek()] > arr[i]) {
                    int idx = stack.pop();
                    long lcnt = idx - stack.peek();
                    long rcnt = i - idx;
                    long cnt = lcnt * rcnt;
                    //这个乘法可能溢出所以需要用long
                    sum +=  cnt*arr[idx];
                }
                stack.push(i);
            }
        }
        return (int)(sum % mod);
    }
}