Problem
Given an array of integers arr, find the sum of min(b)
, where b
ranges over every (contiguous) subarray of arr
. Since the answer may be large, return the answer modulo 109 + 7
.
Example 1:
Input: arr = [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.
Example 2:
Input: arr = [11,81,94,43,3]
Output: 444
Constraints:
1 <= arr.length <= 3 * 104
1 <= arr[i] <= 3 * 104
Solution
/**
* @param {number[]} arr
* @return {number}
*/
var sumSubarrayMins = function(arr) {
var stack = [];
var rightBiggerNums = Array(arr.length).fill(1);
for (var i = 0; i <= arr.length; i++) {
while (stack.length && (i === arr.length || arr[i] < arr[stack[stack.length - 1]])) {
var index = stack.pop();
rightBiggerNums[index] = i - index;
}
stack.push(i);
}
stack = [];
var leftBiggerNums = Array(arr.length).fill(1);
for (var i = arr.length - 1; i >= -1; i--) {
while (stack.length && (i === -1 || arr[i] <= arr[stack[stack.length - 1]])) {
var index = stack.pop();
leftBiggerNums[index] = index - i;
}
stack.push(i);
}
var sum = 0;
var mod = Math.pow(10, 9) + 7;
for (var i = 0; i < arr.length; i++) {
sum += rightBiggerNums[i] * leftBiggerNums[i] * arr[i];
sum %= mod;
}
return sum;
};
Explain:
Monotonic stack, be careful about duplicate nums.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).