907. Sum of Subarray Minimums

Difficulty:
Related Topics:
Similar Questions:

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:

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: