【亡羊补牢】挑战数据结构与算法第7期 LeetCode 907. 子数组的最小值之和（单调栈的讨论，学习大佬の巧妙解法）

程序员文章站 2022-03-11 23:30:23

...

仰望星空的人，不应该被嘲笑

题目描述

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

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

示例：

输入：[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。

提示：

1 <= A <= 30000
1 <= A[i] <= 30000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-subarray-minimums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

搬运 jack-108大佬的题解：

既然是求子数组中最小值的和，就是求以 A[i] 作为最小数能构成的数组有多少个。

比如 [2,4,1,2] ,以1 为最小数。能构成的数组数为 (2+1)*(1+1) ，2 表示 1左面有两个比它大的数，1 表示 1 右面有一个比它大的数。

用单调栈求出 A[i] 对应的左右最近比 A[i] 小的数，记索引为 prev,next，A[i]为最小数能形成的数组为

(i-prev[i])*(next[i]-i)

这里为什么没有加 1 了呢，因为 prev[i]已经是比 A[i] 小的数了，能和 A[i] 形成数组的都是比 A[i] 大的数。

我的解题方式：

注释已经足够详细，还是补充一下，我参考了大佬的解题代码，只不过我是直接求出来了以当前 A[i] 为最小值的子数组左右两边大于或等于当前值的个数。这样后续求和直接相乘即可。（不过这里要强调一下，如果左边设置大于等于了，右边就只能是大于了，不然会重复计算相等的值）

开始有点看不懂大佬为啥左边初始化为 -1，右边初始化为 A.length 。假如我们遇到了这种情况，左边都比当前 A[i] 要大，那我们维护的单调递减栈就会不断出栈，不断出栈，直到栈为空为止，此时左边个数应该为 i+1（从 0 开始计数嘛），那么这部分大佬设为 -1 就很巧妙了，问题也就自然明白啦，个人感觉自己写的还是比较好理解一点，不然直接弄一个 -1 ，第一次用单调栈，还是不太熟…

那么对于右边初始化为 A.length ，也是同理啦，当右边都比当前 A[i] 要大，那我们维护的单调递减栈就会不断出栈，不断出栈，直到栈为空为止，此时右边个数应该为 A.length-i（不用+1的原因是从0计数），那么这部分大佬设为 A.length 就很巧妙了，依旧清晰明了。

/**
 * @param {number[]} A
 * @return {number}
 */
var sumSubarrayMins = function(A) {
  let mod = 1e9+7
  // 维护一个栈
  let stack = []
  // 求以A[i]为最小值的子数组左边大于或等于自己的个数
  let prev = []
  for(let i=0;i<A.length;i++){
    while(stack.length && A[stack[stack.length-1]] >= A[i]) stack.pop()
    // 如果栈为空，即左边都比自己大，则返回i+1，否则返回i-栈顶元素（即保存的下标值）
    prev[i] = stack.length ? i - stack[stack.length-1] : i+1
    stack.push(i)
  }
  stack = []
  // 求以A[i]为最小值的子数组右边大于自己的个数（没有等号是因为不会重复计算相等的值）
  let nextv = []
  for(let i=A.length-1;i>=0;i--){
    while(stack.length && A[stack[stack.length-1]] > A[i]) stack.pop()
    // 如果栈为空，即右边都比自己大，则返回A.length-i，否则返回栈顶元素（即保存的下标值）-i
    nextv[i] = stack.length? stack[stack.length-1] - i : A.length-i
    stack.push(i)
  }
  let sum = 0
  for(let i=0;i<A.length;i++){
    // 以A[i] 为最小值的子数组的组合共有prev[i]*nextv[i]种情况，那么和的话乘以A[i]累加即可
    sum += (prev[i]*nextv[i]*A[i])
    // 按题意，进行取模运算
    sum %= mod
  }
  return sum
};