907. 子数组的最小值之和

1. 求所有子数组的最小值，可以转换为，求每个数能在子数组中作为最小值的贡献次数。
2. 所以需要知道每个数能在左边有多少次数，在右边有多少次数。
   1. 可以利用单调栈
   2. 当arr[i] >= stack.peek()时，下标i入栈
   3. 当arr[i] < stack.peek()时，将栈顶元素出栈int pop = stack.pop()
   4. pop作为最小值的范围为，左边[stack.peek(), pop]，右边[pop, i-1]
   5. 遍历完数组后，若栈中不为空，将元素出栈
   6. 出栈的每个数，它们的范围为，左边[stack.peek(), pop]，右边[pop, arr.length]
3. 根据组合原理，将左右次数相乘，即得该数作为子数组的贡献次数

approach 1，单调栈+乘法组合运用

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] l = new int[n];
        Arrays.fill(l, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && arr[i] < arr[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                l[i] = -1;
            } else {
                l[i] = stack.peek();
            }
            stack.push(i);
        }
        
        stack.clear();
        int[] r = new int[n];
        Arrays.fill(r, n);
        for (int i = n-1; i >= 0; i--) {
            while (!stack.empty() && arr[i] <= arr[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                r[i] = n;
            } else {
                r[i] = stack.peek();
            }
            stack.push(i);
        }

        int mod = (int) 1e9 + 7;
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += 1L * arr[i] * (i - l[i]) * (r[i] - i) % mod;
            res %= mod;
        }
        return (int) res;
    }
}

class Solution {
    public int sumSubarrayMins(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int mod = (int) 1e9 + 7;
        int n = arr.length;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && arr[i] <= arr[stack.peek()]) {
                int p = stack.pop();
                int left = stack.empty() ? -1 : stack.peek();
                int right = i;
                ans += 1L * (p - left) * (right - p) * arr[p] % mod;
            }
            stack.push(i);
        }

        while (!stack.empty()) {
            int p = stack.pop();
            int left = stack.empty() ? -1 : stack.peek();
            int right = n;
            ans += 1L * (p - left) * (right - p) * arr[p] % mod;
        }
        return (int) (ans % mod);
    }
}

利用两个数组将当前值作为左右两边最小值的边界距离记录下来，最后乘起来即可

class Solution {
    static int mod = (int) 1e9 + 7;
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] left = new int[n], right = new int[n];
        int[] stack = new int[n];
        int p = -1;
        for (int i = 0; i < n; i++) {
            while (p != -1 && arr[i] < arr[stack[p]]) {
                int pop = stack[p--];
                right[pop] = i - pop;
            }
            left[i] = p == -1 ? (i + 1) : (i - stack[p]);
            stack[++p] = i;
        }

        while (p != -1) {
            int pop = stack[p--];
            right[pop] = n - pop;
        }
        long ans = 0;
        for (int i = 0; i < n; i++) 
            ans = (ans + (1L * left[i] * right[i] * arr[i] % mod)) % mod;
        return (int) ans;
    }
}