907 Sum of Subarray Minimums

907. Sum of Subarray Minimums

1. Question

Given an array of integersA, find the sum ofmin(B), whereBranges over every (contiguous) subarray ofA.

Since the answer may be large,return the answer modulo10^9 + 7.

Example 1:

Input: [3,1,2,4]

Output: 17

Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

1. 1 <= A.length <= 30000

2. 1 <= A[i] <= 30000

2. Implementation

(1) Stack

思路:

class Solution {
    public int sumSubarrayMins(int[] A) {
        int n = A.length;
        Stack<int[]> stack = new Stack();
        int[] left = new int[n];
        int[] right = new int[n];

        stack.push(new int[] {-1, -1});

        for (int i = 0; i < n; i++) {
            int curNum = A[i];
            while (!stack.isEmpty() && stack.peek()[0] >= curNum) {
                stack.pop();
            }

            if (stack.peek()[1] == -1) {
                left[i] = i;
            }
            else {
                left[i] = i - stack.peek()[1] - 1;
            }

            stack.push(new int[] {curNum, i});
        }

        stack = new Stack();
        stack.push(new int[] {-1, -1});

        for (int i = n - 1; i >= 0; i--) {
            int curNum = A[i];
            while (!stack.isEmpty() && stack.peek()[0] > curNum) {
                stack.pop();
            }

            if (stack.peek()[1] == -1) {
                right[i] = n - i - 1;
            }
            else {
                right[i] = stack.peek()[1] - i - 1;
            }

            stack.push(new int[] {curNum, i});
        }

        long sum = 0;

        for (int i = 0; i < n; i++) {
            sum += ((left[i] + 1) * (right[i] + 1) * A[i]) % 1000000007;
            sum %= 1000000007;
        }
        return (int)sum;
    }
}

3. Time & Space Complexity

(1) Stack: 时间复杂度, 空间复杂度