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 <= A.length <= 30000
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;
}
}