题目描述

leetcode907. 子数组的最小值之和

给定一个整数数组 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 <= arr.length <= 3 * 104
  • 1 <= arr[i] <= 3 * 104

 

题解——单调栈典型题——求最近的更小元素

力扣最近的每日一题经常出单调栈、单调队列这一类题，听上去唬人，但是知道它们的作用后，基本是套模板了。

思路

如果我们枚举所有子数组，再逐个求最小值，显然是行不通的。应该逆向思考这个问题，即求最小值为某个值的区间个数，由于最小值一定在arr中产生，我们可以遍历每一个值，求出以它为最小值的区间数目。
如何界定呢？方法是找到左右两边最近的更小值的位置，这样，(left,now]都可以作为起点，[now,right)的都可以作为终点，一乘就可以了。

举个例子

对题目的第二个例子进行具体计算，读者也可以自己算算验证一下。
arr = [11,81,94,43,3]

  • 对于11，左边没有更小值，右边更小值为3，那么，只能以11为起点，终点可以选11，81，94，43，共4个数组，对答案的贡献就是4*11=44
  • 对于81，左边更小值为11，右边更小值为43，那么，可以以81为起点，81，94为终点，共两个数组，对答案的贡献为2*81=162
  • 对于94，左边更小值为81，右边更小值为43，只能以自身为起点终点，共一个数组，贡献94
  • 对于43，左边更小值为11，右边更小值为3，可以以81，94，43为起点，43为终点，共三个数组，对答案的贡献为3*43=129
  • 对于3，左边没有更小值，右边没有更小值，可以以11，81，94，43，3为起点，3为终点，共五个数组，对答案的贡献为5*3=15
  • 最终结果就是累加起来，44+162+94+129+15=444

更一般来说，如果当前位置坐标为i，左边更小值位置为pos1，右边为pos2，则贡献就是(i-pos1)*(pos2-i)*arr[i]。特别地，如果左边没有更小值，pos1=-1，如果右边没有更小值，pos2=size。

单调栈

接下来的问题就是，如何快速地求出左右的最近更小值位置，这就要利用单调栈。我们维护一个单调递增栈，里面存放下标(下文的值都是下标对应的值)。对于每一个值，如果栈顶>=当前值，就出栈，直到栈为空或者栈顶更小，此时栈顶就是最近更小值的位置，然后将当前下标入栈。这样，每次可以获取左边更小值的位置。要想获取右边的位置，很直白的做法是倒着来一遍，不过，其实当栈顶>=当前值时，当前下标就是栈顶右边更小值的位置，所以我们只需要在出栈时进行计算就行了，为了全部计算，我们人为地在右边添加一个最小值，保证最后全部出栈计算完毕。

代码

具体代码如下，可以对着注释理解一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        arr.push_back(INT_MIN);//为了确保全部计算，人为添加一个下界
        vector<int> prePos(arr.size());//维护前一个更小元素的位置，在入栈时得出
        stack<int> stk;//单调递减栈，保存下标
        long long ans=0,mod=1e9+7;
        for(int i=0;i<arr.size();++i)
        {
            while(!stk.empty()&&arr[stk.top()]>=arr[i])//出栈并进行计算
            {
                int now=stk.top();
                ans=(ans+1LL*(now-prePos[now])*(i-now)*arr[now])%mod;
                stk.pop();
            }
            prePos[i]=stk.empty()?-1:stk.top();//保存前一个更小元素的位置
            stk.push(i);
        }
        return ans;
    }
};