题目

题目来源：力扣（LeetCode）

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
示例 2：

输入：arr = [11,81,94,43,3]
输出：444

  1. /**
  2.  * @param {number[]} arr
  3.  * @return {number}
  4.  */
  5. // 1.题目的关键在于找到A[i]属于的区间, 满足A[i]为该区间内的最小值。
  6. // 2.这里使用单调递增栈巧妙地找到该区间的左右边界：
  7.   // 单调栈的前一个元素为小于该元素的第一个索引, 即为区间的左边界
  8.   // 单调栈的元素出栈时, 说明其后面出现了比该元素更小的值, 即为区间的右边界
  9. // 3.就是将第i个元素入队列，求出前面区间的跨度，就是第I个元素贡献的和值，再加上sum3（假设前面
  10. // 有3个值，前三个和值）
  11. var sumSubarrayMins = function (arr) {
  12.   let stack = [];
  13.   let mod_num = 1e9 + 7;
  14.   let ans = 0;
  15.   let sum = new Array(arr.length + 1);
  16.   sum[0] = 0;
  17.   for (let i = 0; i < arr.length; i++) {
  18.     while (stack.length && arr[i] <= arr[stack[stack.length - 1]]) stack.pop();
  19.     let index = stack.length ? stack[stack.length - 1] : -1;
  20.     stack.push(i);
  21.     sum[stack.length] = (sum[stack.length - 1] + arr[i] * (i - index)) % mod_num;
  22.     ans += sum[stack.length];
  23.     ans %= mod_num;
  24.   }
  25.   return ans;
  26. }

借鉴：
https://leetcode-cn.com/problems/sum-of-subarray-minimums/solution/guan-fang-er-jie-fa-javascript-xiang-jie-by-jack-1/ https://leetcode-cn.com/problems/sum-of-subarray-minimums/solution/dan-diao-zhan-zuo-you-liang-bian-di-yi-g-ww3n/