# 0907. Sum of Subarray Minimums
###### tags: `Leetcode` `Medium` `Stack` `Count Subarray by Element`
Link: https://leetcode.com/problems/sum-of-subarray-minimums/
## 思路 $O(N)$ $O(N)$
最终结果 = 每个element * 以它为minimum的subarray数量
算left和right的值是用单调递增stack
原因: 单调栈可以用来**找左边/右边 第一个(离他最近的)比它大/比它小的数字** 找离他最远的比它小的数字和找离他最近的比它大的数字是一样的
## Code

class Solution {
        public int sumSubarrayMins(int[] A) {
        Stack<Integer> s = new Stack<>();
        int n = A.length, j, k;
        long res = 0, mod = (long)1e9 + 7;
        for (int i = 0; i <= n; i++) {
            while (!s.isEmpty() && A[s.peek()] > (i == n ? 0 : A[i])) {
                j = s.pop();
                k = s.isEmpty() ? -1 : s.peek();
                res = (res + (long)A[j] * (i - j) * (j - k)) % mod;

            }
            s.push(i);
        }
        return (int)res;
    }
}