题目简介：
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
示例 1：
1
2
3
4
5
| 输入：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。
|
思路：
对于元素arr[i]，我们首先找到左右两边的端点，使其能在这个范围内为最小值。
假设左端点为L，右端点为R，则范围为(L, R)。【注意都是开区间】
最小值为arr[i]的子数组的左端点可以设置为L + 1, ..., i;
右端点可以设置为i, i + 1, ... R - 1。
因此arr[i]作出的贡献为arr[i] * (i - L) * (R - i)。
假设数组为[2, 4, 2, 3]，为了避免重复计算2的子数组，我们把寻找右端点的条件改为小于等于arr[i]的下标，左端点依然为小于arr[i]的数。
这样以第一个2为最小值的子数组就不会越界包含第二个2了，从而解决了重复的问题。
接下来的问题就转换为如何高效的求每个元素的左右区间了。
我们可以注意到，计算左边界时，若arr[i] <= arr[j], j < i，那么当arr[k] > arr[j], k > i时，arr[k] > arr[i]也必定成立，也就是说此时的左边界必定不可能是j了，所以我们可以弹出j了。
这样我们可以保证会形成一个递增序列，我们进行删除和添加操作都是在右端，所以我们选择栈。
计算右边界时，我们从后往前遍历，弹出操作与左边界一样（注意是arr[i] < arr[j]）。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int mod = pow(10, 9) + 7;
vector<int> left(arr.size(), -1);
vector<int> right(arr.size(), arr.size());
stack<int> stk;
for(int i = 0; i < arr.size(); i++){
while(!stk.empty() && arr[i] <= arr[stk.top()])
stk.pop();
if(!stk.empty())
left[i] = stk.top();
stk.push(i);
}
while(!stk.empty())
stk.pop();
for(int i = arr.size() - 1; i >= 0; i--){
while(!stk.empty() && arr[i] < arr[stk.top()])
stk.pop();
if(!stk.empty())
right[i] = stk.top();
stk.push(i);
}
long res = 0;
for(int i = 0; i < arr.size(); i++){
res = (res + (long) arr[i] * (i - left[i]) * (right[i] - i)) % mod;
}
return res;
}
};
|
