题目描述

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;
}
};