题目描述
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
提示：
-
1 <= arr.length <= 3 * 10^4
-
1 <= arr[i] <= 3 * 10^4
示例
输入：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。 思路
这是今天的每日一题，题意描述非常简单。就是给一个数组，找出这个数组所有的子数组，对每个子数组求个
min
，再把结果相加。
想法一：暴力+单调栈
// C++
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int ans = 0, n = arr.size(), MOD = 1e9 + 7;
// 单调递增的单调栈
vector<int> v;
// 枚举所有以i为右端点的子数组
for (int i = 0; i < n; i++) {
while (!v.empty() && arr[v.back()] >= arr[i]) v.pop_back();
v.push_back(i);
int k = 0;
for (int j = 0; j <= i; j++) {
while (v[k] < j) k++;
ans += arr[v[k]];
ans %= MOD;
}
}
return ans;
}
}; 提交结果：TLE(Time Limit Exceed)。
反思：这样用单调栈其实没什么卵用，效率甚至比直接暴力更差。我上面这个的想法是，枚举子数组的右端点
i
，然后再枚举左端点
j
，然后
v
是用单调栈存了
[0, i]
中的最小值。然后每次尝试找
[j, i]
内的最小值，都是从单调栈的第一个元素开始找。这样搞，本来枚举子数组的时间复杂度就已经是 了，每次找某个子数组的最小值，花的时间还不是固定的 。脑子真是秀逗了。比纯暴力还拉跨。下面写个纯暴力的，时间复杂度标准的 。
typedef long long LL;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
LL ans = 0, MOD = 1e9 + 7;
// 枚举子数组右端点
for (int i = 0; i < arr.size(); i++) {
// 枚举左端点j, 从右往左枚举, 并维护最小值
int t = arr[i];
for (int j = i; j >= 0; j--) {
t = min(t, arr[j]);
ans += t;
ans %= MOD;
}
}
return (int) ans;
}
}; 但是这道题的数据范围是
10^4
， 就已经达到了
10^8
,一定会超时。
我们看看可以如何优化，先随便构造一组数据进行观察
5 3 2 6 8 1 9
[5]
[5 3]
[5 3 2]
[5 3 2 6]
[5 3 2 6 8]
[5 3 2 6 8 1]
[5 3 2 6 8 1 9]
[3]
[3 2]
[3 2 6]
[3 2 6 8]
[3 2 6 8 1]
[3 2 6 8 1 9]
[2]
[2 6]
[2 6 8]
[2 6 8 1]
[2 6 8 1 9]
[6]
[6 8]
[6 8 1]
[6 8 1 9]
[8]
[8 1]
[8 1 9]
[1]
[1 9]
[9] 我们观察一下，可以看到，有些数字其实是作为了多个子数组的最小值的。比如3，作为了
[5 3]
，
[3]
的最小值，2作为了
[5 3 2]
，
[5 3 2 6]
，
[5 3 2 6 8]
,…等子数组的最小值。
我们计算所有子数组的最小值的和，肯定是不能通过子数组来算了，因为只要通过枚举子数组来算，子数组的个数就一定是。
上面我们看到，某个值
x
，可能是会作为多个子数组的最小值的。那么我们可以换个角度，不从子数组来求最小值，而从最小值来求子数组。
什么意思呢？
对于某个位置
i
的数
arr[i]
，我们看一下，最小值为
arr[i]
的子数组，共有多少个。要想使得子数组的最小值为
arr[i]
，首先子数组要包含
i
这个位置，其次，
arr[i]
要小于等于子数组中其他所有的数。
于是，我们可以看到，只需要求解一下，以
arr[i]
为最小值，往左往右最远能扩展到什么位置，即可。假设往左最远能到的位置是
L
,往右最远能到的位置是
R
。那么区间
[L, R]
内的所有数都是大于等于
arr[i]
的。而
L - 1
和
R + 1
，要么已经越界，要么其数字比
arr[i]
更小。
我们可以将
[L, R]
称作是
arr[i]
的辐射范围。由于子数组需要包含
i
这个位置，那么子数组的左端点的有效取值范围是
[L, i]
，子数组右端点的有效取值范围是
[i, R]
。根据乘法原理，子数组的个数就是
左端点的个数 × 右端点的个数
，即
(i - L + 1) × (R - i + 1)
，令其为
num
。那么共有
num
个子数组的最小值为
arr[i]
，我们可以通过一次运算，将这
num
个子数组的最小值的和算出来，即
num × arr[i]
。
于是，只要遍历整个数组，对每个
i
[0, n - 1]
，我们都计算一下，看以
arr[i]
作为最小值的子数组共有多少个，然后将结果进行累加，就能得到最终答案。这样的计算方式，只需要一次遍历，时间复杂度是 。
能这样计算的前提是，对于每个位置
i
，我们都求得了其辐射范围
[L, R]
。所以现在的问题变成了，如何求得某个
i
的辐射范围。
根据定义，
arr[i]
是整个
[L, R]
区间内的最小值。很明显，我们只要从
i
开始往左，往右，找到第一个比
arr[i]
更小的数，就可以了。假设
i
左侧第一个小于
arr[i]
的位置是
L - 1
，
i
右侧第一个小于
arr[i]
的位置是
R + 1
。那么区间
[L, R]
内全部元素，没有比
arr[i]
更小的了，这样就找到了
i
的辐射范围
[L, R]
。
那么现在，问题就变成了，如何找到
i
左(右)侧第一个小于
arr[i]
的数。
一看到这种描述，什么
找左(右)侧第一个比其小(大)的数
，就应当立刻想到单调栈。单调栈就是干这个的！
设
left[i]
表示
i
左侧第一个小于
arr[i]
的位置，
right[i]
表示
i
右侧第一个小于
arr[i]
的位置。那么我们只需要两次遍历，就能求出所有的
left[i]
和
right[i]
。于是我们写出如下代码
typedef long long LL;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int n = arr.size(), MOD = 1e9 + 7;
vector<int> left(n, -1), right(n, n);
stack<int> stk;
// 求左侧第一个比其小, 栈中应当单调递增
for (int i = 0; i < n; i++) {
// 栈非空且栈顶 >= arr[i], 出栈
while (!stk.empty() && arr[stk.top()] >= arr[i]) stk.pop();
// 找到左侧第一个比其小的位置
// 栈如果为空, 则为-1, 前面已经初始化过了
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
// 清空栈, 注: C++中的stack没有clear方法
while (!stk.empty()) stk.pop();
// 求右侧第一个比其小
for (int i = n - 1; i >= 0; i--) {
// 栈非空且栈顶 >= arr[i], 出栈
while (!stk.empty() && arr[stk.top()] >= arr[i]) stk.pop();
// 栈如果为空, 则为n, 前面已经初始化过了
if (!stk.empty()) right[i] = stk.top();
stk.push(i);
}
LL ans = 0;
for (int i = 0; i < n; i++) {
// 辐射范围的左端点 L = left[i] + 1, 右端点 R = right[i] - 1
// 这也是为什么 left[i]初始化为-1, right[i]初始化为n
// 左端点的有效区间为 [L, i], 总个数为 i - L + 1 = i - left[i]
// 右端点的有效区间为 [i, R], 总个数为 R - i + 1 = right[i] - i
LL t = arr[i] * (i - left[i]) * (right[i] - i);
ans = (ans + t) % MOD;
}
return ans;
}
}; 但是到这里还没有结束，上述代码提交后结果是WA (Wrong Answer)
来看一组错误数据:
[1 5 3 7 4 3]
观察到这个数组里有2个3，第一个3的辐射范围是
[1, 5]
，第二个3的辐射范围也是
[1, 5]
。我们发现，以第一个3为最小值的一个子数组是[5,3,7,4,3]，以第二个3为最小值的一个子数组是[5,3,7,4,3]，容易看到，这是同一个子数组。但我们计算时，这个子数组的最小值被加了2次。所以我们需要去重。
我自己的思路就卡在这里了，我想了很久都没想到要如何去重。简单记录下自己的想法：
假设数
x
的辐射范围内，有2个
x
，比如
[?,?,x,?,?,?,x,?,?]
。
则有哪些子数组会重复呢？答案是，左端点在第一个
x
位置的左侧(包含x的位置)，右端点在第二个
x
的右侧(包含x的位置)，这些子数组会被重复计算一次。那么我们需要额外维护
x
出现的位置才行。并且，假设辐射范围内有更多的
x
，则计算重复的子数组的个数将会变得更加复杂。于是便卡在这里走不下去了。
下面看看正确的做法是什么？只需要在求解辐射范围时，一侧找到第一个小于
arr[i]
的位置，另一侧找到第一个小于等于
arr[i]
的位置。
比如，左侧找到第一个小于等于
arr[i]
的位置，右侧找到第一个小于
arr[i]
的位置。我们来看下会有什么不同。
[1 5 3 7 4 3]
对于第一个3，左侧第一个小于等于3的位置是0，右侧第一个小于3的位置是6，那么其辐射范围为
[1, 5]
。
对于第二个3，左侧第一个小于等于3的位置是2，右侧第一个小于3的位置是6，那么其辐射范围为
[3, 5]
即，第一个3的有效区间是
[5 3 7 4 3]
,第二个3的有效区间是
[7 4 3]
，由于重复的子数组需要满足的条件是，左端点在第一个3左侧，右端点在第二个3右侧。但是我们第二个3的
L
并不能取到第一个3的位置以及更左侧的位置，所以，对于那些左端点在第一个3左侧，右端点在第二个3右侧的子数组，在第一个3的时候已经被算过，且在第二个3时不会再次被计算，对于后续再出现相同的3也一样。如此便能达到不重复计算的目的。
只需要把上述代码稍加修改，在求
left
和
right
时，保证其中一个数组求的是小于等于，另一个求的是小于，即可。
typedef long long LL;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int n = arr.size(), MOD = 1e9 + 7;
vector<int> left(n, -1), right(n, n);
stack<int> stk;
// 求左侧第一个比其小, 栈中应当单调递增
for (int i = 0; i < n; i++) {
// 栈非空且栈顶 >= arr[i], 出栈
while (!stk.empty() && arr[stk.top()] >= arr[i]) stk.pop();
// 找到左侧第一个比其小的位置
// 栈如果为空, 则为-1, 前面已经初始化过了
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
// 清空栈, 注: C++中的stack没有clear方法
while (!stk.empty()) stk.pop();
// 求右侧第一个比其小
for (int i = n - 1; i >= 0; i--) {
// 栈非空且栈顶 >= arr[i], 出栈
while (!stk.empty() && arr[stk.top()] > arr[i]) stk.pop();
// 栈如果为空, 则为n, 前面已经初始化过了
if (!stk.empty()) right[i] = stk.top();
stk.push(i);
}
LL ans = 0;
for (int i = 0; i < n; i++) {
// 辐射范围的左端点 L = left[i] + 1, 右端点 R = right[i] - 1
// 这也是为什么 left[i]初始化为-1, right[i]初始化为n
// 左端点的有效区间为 [L, i], 总个数为 i - L + 1 = i - left[i]
// 右端点的有效区间为 [i, R], 总个数为 R - i + 1 = right[i] - i
LL t = (LL) arr[i] * (i - left[i]) * (right[i] - i);
ans = (ans + t) % MOD;
}
return ans;
}
}; 这样提交就AC啦~
但是遍历了3次，我们看下能不能减少一下遍历的次数呢。答案是可以的。我们观察到，在求解某一侧的时候，就已经能同时求解出另一侧(比如在求解
left
时,已经能同时求出
right
)。
观察这一行：
while (!stk.empty() && arr[stk.top()] >= arr[i]) stk.pop(); 我们是从左往右遍历的，单调栈中存的下标，一定是小于
i
的，而单调栈中要保持递增，当满足这个
while
条件时，对于栈顶元素，就是遇到了其右侧第一个小于等于它的位置。而我们恰好要求一侧是小于，一侧是小于等于。我们将代码修改如下
while (!stk.empty() && arr[stk.top()] >= arr[i]) {
right[stk.top()] = i;
stk.pop();
} 此时我们求出的
left[i]
表示的是左侧第一个小于，
right[i]
表示的是右侧第一个小于等于，恰好满足我们去重的需求。
所以我们可以用一次遍历就求出全部的
left[i]
和
right[i]
。
所以我们可以将3次遍历减少为2次遍历。
typedef long long LL;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int n = arr.size(), MOD = 1e9 + 7;
vector<int> left(n, -1), right(n, n);
stack<int> stk;
// 求左侧第一个比其小, 栈中应当单调递增
for (int i = 0; i < n; i++) {
// 栈非空且栈顶 >= arr[i], 出栈
while (!stk.empty() && arr[stk.top()] >= arr[i]) {
right[stk.top()] = i;
stk.pop();
}
// 找到左侧第一个比其小的位置
// 栈如果为空, 则为-1, 前面已经初始化过了
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
// 清空栈, 注: C++中的stack没有clear方法
while (!stk.empty()) stk.pop();
LL ans = 0;
for (int i = 0; i < n; i++) {
// 辐射范围的左端点 L = left[i] + 1, 右端点 R = right[i] - 1
// 这也是为什么 left[i]初始化为-1, right[i]初始化为n
// 左端点的有效区间为 [L, i], 总个数为 i - L + 1 = i - left[i]
// 右端点的有效区间为 [i, R], 总个数为 R - i + 1 = right[i] - i
LL t = (LL) arr[i] * (i - left[i]) * (right[i] - i);
ans = (ans + t) % MOD;
}
return ans;
}
}; ![241 Different Ways to Add Parentheses（C代码版）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)