Sum of Subarray Minimums

Description

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 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. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

 

Solution(javascript)

/*
 * @lc app=leetcode id=907 lang=javascript
 *
 * [907] Sum of Subarray Minimums
 */

// @lc code=start
/** O(n^2) 遍历所有情况
 * @param {number[]} A
 * @return {number}
 */
// const sumSubarrayMins = function (A) {
//   let result = 0
//   for (let i = 0; i < A.length; i++) {
//     let min = A[i]
//     result += min
//     for (let j = i + 1; j < A.length; j++) {
//       min = Math.min(min, A[j])
//       result += min
//     }
//   }
//   return result % ((10 ** 9) + 7)
// }


/**  monotone stack
 * @param {number[]} A
 * @return {number}
 */
const sumSubarrayMins = function (A) {
  let stack = []
  const left = []
  const right = []


  for (let i = 0; i < A.length; i++) {
    const num = A[i]
    let count = 1
    while (stack.length && num <= stack[stack.length - 1][0]) { // NOTE <= 去重复
      count += stack.pop()[1]
    }
    stack.push([num, count])
    left[i] = count
  }
  stack = []
  for (let i = A.length - 1; i >= 0; i--) {
    const num = A[i]
    let count = 1
    while (stack.length && num < stack[stack.length - 1][0]) { // NOTE <
      count += stack.pop()[1]
    }
    stack.push([num, count])
    right[i] = count
  }
  const result = A.reduce((acc, num, i) => acc + num * (left[i] * right[i]), 0)
  return result % ((10 ** 9) + 7)
}