[LeetCode] Problem 907 - Sum of Subarray Minimums

Posted on | In ,

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

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

Example

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// res = sum(A[i] * f(i))，其中f(i)是子数组的数量，A[i]是最小值。
// f(i) = (left[i] + 1) * (right[i] + 1)
// left[i]，能在A[i]左侧取得的最长宽度，使得在这个范围内A[i]是最小值,且都大于A[i]
// right[i], 能在A[i]右侧取得的最长宽度，使得在这个范围内A[i]是最小值，且都大于等于A[i]
public int sumSubarrayMins(int[] A) {
    int result = 0;
    int mod = (int) 1e9 + 7;
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i <= A.length; i++) {
        int next = (i == A.length) ? -1 : A[i];

        while (!stack.isEmpty() && next < A[stack.peek()]) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            result = (result + A[j] * (j - k) * (i - j)) % mod;
        }

        stack.push(i);
    }

    return result;
}