907. Sum of Subarray Minimums

这个题的关键在于
当我们知道 譬如 [1, 5, 6, 9, 2, 4]
2 是[5- 4] 范围内最小的，那么以2 为min的subarray有多少呢？
是以2为结尾的subarray 和以2为开始的subarray的combination(multiplification)
因为它们必须包含2
后面的Stack比较straightforward

95.07 %
class Solution {
    public int sumSubarrayMins(int[] A) {
        // [3,1,2,4]
        //  2 as min -> left [2(2)] right[2(2), 4(3)]
        //  2 * (2 - 2 + 1) * (3 - 2 + 1) = 2 * 2(2 / 2,4) = 4
        //  [3,2,2,4]
        //  2 as min, left[3(0), 2(1)]  right[2(1), 2(2), 4(3)]
        //  2 * 2 * 3 = 6
        // left[>]  right[>=]
        if (A == null) {
            return 0;
        }
        // i = 2
        // curr =
        // 1 2 4
        //
        // index
        int len = A.length;
        Deque<Integer> stack = new ArrayDeque<>();
        long sum = 0;
        long mod = (long)(1e9 + 7);
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && A[stack.peekFirst()] >= A[i]) {
                int curr = stack.removeFirst();
                sum += (long)A[curr] * (curr - (stack.isEmpty() ? -1 : stack.peekFirst())) * (i - curr);
                sum = sum % mod;
            }
            stack.addFirst(i);
        }
       
        while (!stack.isEmpty()) {
            int curr = stack.removeFirst();
            sum += (long)A[curr] * (curr - (stack.isEmpty() ? -1 : stack.peekFirst())) * (len - curr);
            sum = sum % mod;
        }
        return (int)sum;
    }
}