2022-11-25.md

题目

907. Sum of Subarray Minimums

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.

思路

1. 包含arr[i]的subarry里，以arr[i]为最小值的个数=left * right
2. 单调递增的stack用来计算left和right

代码

var sumSubarrayMins = function(arr) {
  const m = 10 ** 9 + 7
  const stack = [-1]
  arr.push(0)
  let sum = 0
  for (let i = 0; i < arr.length; i++) {
    while (arr[i] < arr[stack[stack.length - 1]]) {
      const mid = stack.pop()
      const right = i - mid
      const left = mid - stack[stack.length - 1]
      sum += (left * right * arr[mid])
      sum %= m
    }
    stack.push(i)
  }
  return sum
};