来源：
力扣（LeetCode）
描述：
给定一个整数数组
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 * 10
4
-
1 <= arr[i] <= 3 * 10
4
方法一：单调栈
考虑所有满足以数组 arr 中的某个元素 arr[i] 为最右且最小的元素的子序列个数 C[i]，那么题目要求求连续子数组的最小值之和即为
，其中数组 arr 的长度为 n。我们必须假设当前元素为最右边且最小的元素，这样才可以构造互不相交的子序列，否则会出现多次计算，因为一个数组的最小值可能不唯一。
经过以上思考，我们只需要找到每个元素 arr[i] 以该元素为最右且最小的子序列的数目 left[i]，以及以该元素为最左且最小的子序列的数目 right[i]，则以 arr[i] 为最小元素的子序列的数目合计为 left[i] × right[i]。当然为了防止重复计算，我们可以设 arr[i] 左边的元素都必须满足小于等于 arr[i]， arr[i] 右边的元素必须满足严格小于 arr[i]。当然这就变成求最小的下标 j ≤ i，且连续子序列中的元素 arr[j], arr[j+1], ⋯, arr[i] 都满足大于等于 arr[i]，以及最大的下标 k > i 满足连续子序列 arr[i+1], arr[i+1], ⋯, arr[k] 都满足严格大于 arr[i]。上述即转化为经典的单调栈问题，即求数组中当前元素 x 左边第一个小于 x 的元素以及右边第一个小于等于 x 的元素。
对于数组中每个元素 arr[i]，具体做法如下：
-
求左边第一个小于 arr[i] 的元素：从左向右遍历数组，并维护一个单调递增的栈，遍历当前元素 arr[i]，如果遇到当前栈顶的元素大于等于 arr[i] 则将其弹出，直到栈顶的元素小于 arr[i]，栈顶的元素即为左边第一个小于 arr[i] 的元素 arr[j]，此时 left[i] = i − j。
-
求右边第一个大于等于 arr[i] 的元素：从右向左遍历数组，维护一个单调递增的栈，遍历当前元素 arr[i]，如果遇到当前栈顶的元素大于 arr[i] 则将其弹出，直到栈顶的元素小于等于 arr[i]，栈顶的元素即为右边第一个小于等于 arr[i] 的元素 arr[k]，此时 right[i] = k − i。
-
连续子数组 arr[j], arr[j+1], ⋯, arr[k] 的最小元素即为 arr[i]，以 arr[i] 为最小元素的连续子序列的数量为 (i−j) × (k−i)。
根据以上结论可以知道，所有子数组的最小值之和即为
维护单调栈的过程线性的，因为只进行了线性次的入栈和出栈。
代码：
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int n = arr.size();
vector<int> monoStack;
vector<int> left(n), right(n);
for (int i = 0; i < n; i++) {
while (!monoStack.empty() && arr[i] <= arr[monoStack.back()]) {
monoStack.pop_back();
}
left[i] = i - (monoStack.empty() ? -1 : monoStack.back());
monoStack.emplace_back(i);
}
monoStack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!monoStack.empty() && arr[i] < arr[monoStack.back()]) {
monoStack.pop_back();
}
right[i] = (monoStack.empty() ? n : monoStack.back()) - i;
monoStack.emplace_back(i);
}
long long ans = 0;
long long mod = 1e9 + 7;
for (int i = 0; i < n; i++) {
ans = (ans + (long long)left[i] * right[i] * arr[i]) % mod;
}
return ans;
}
};
执行用时：76 ms, 在所有 C++ 提交中击败了68.14%的用户
内存消耗：41.2 MB, 在所有 C++ 提交中击败了63.99%的用户
复杂度分析
时间复杂度：O(n)，其中 n 为数组的长度。利用单调栈求出每个元素为最小值的子序列长度需要的时间为 O(n)，求出连续子数组的最小值的总和需要的时间为 O(n)，因此总的时间复杂度为 O(n)。
空间复杂度：O(n)。其中 n 为数组的长度。我们需要保存以每个元素为最小元素的子序列长度，所需的空间为 O(n)。
author：
LeetCode-Solution
方法二：动态规划
设 s[j][i] 表示子数组 [arr[j], arr[j+1], ⋯, arr[i]] 的最小值，则可以推出所有连续子数组的最小值之和为
对于每个以 i 为最右的子数组最小值之和为
我们只需要求出以每个元素 arr[i] 为最右的子数组最小值之和，即可求出所有的子数组的最小值之和。每当我们减少 j 时，子序列的最小值可能会有关联，事实上我们可以观察到 s[j−1][i] = min(s[j][i],arr[j−1])。
假设当前数组为: arr=[1,7,5,2,4,3,9]，当 i = 5 时，所有以索引 j 为起点且以 i 结尾的连续子序列为:
上述序列的最小值分别为 [3, 3, 2, 2, 2, 1]，可以发现重要点是 j = 5, j = 3, j = 0，分别是 j 从 i 开始向左移动遇到的最小值的位置。如下图所示:
设以 arr[i] 为最右且最小的最长子序列长度为 k：
-
当 j >= i – k + 1 时：连续子序列 [arr[j]，arr[j+1],⋯，arr[i]] 的最小值为 arr[i]，即 s[j][i] = arr[i]。
-
当 j < i – k + 1 时：连续子序列 [arr[j]，arr[j+1],⋯，arr[i]] 的最小值一定比 arr[i] 更小，通过分析可以知道它的最小值 s[j][i] = min(s[j][i−k],arr[i]) = s[j][i−k]。
则可以知道递推公式如下：
我们维护一个单调栈，很容易求出元素 x 的左边第一个比它小的元素，即求出以 x 为最右且最小的子序列的最大长度，子数组的最小值之和即为
具体解法过程如下：
-
从左向右遍历数组并维护一个单调递增的栈，如果栈顶的元素大于等于当前元素 arr[i] 则弹出栈，此时栈顶的元素即为左边第一个小于小于当前值的元素；
-
我们求出以当前值为最右且最小的子序列的长度 k，根据上述递推公式求出 dp[i]，最终的返回值即为
代码：
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int n = arr.size();
long long ans = 0;
long long mod = 1e9 + 7;
stack<int> monoStack;
vector<int> dp(n);
for (int i = 0; i < n; i++) {
while (!monoStack.empty() && arr[monoStack.top()] > arr[i]) {
monoStack.pop();
}
int k = monoStack.empty() ? (i + 1) : (i - monoStack.top());
dp[i] = k * arr[i] + (monoStack.empty() ? 0 : dp[i - k]);
ans = (ans + dp[i]) % mod;
monoStack.emplace(i);
}
return ans;
}
};
执行用时：68 ms, 在所有 C++ 提交中击败了85.68%的用户
内存消耗：39.8 MB,在所有 C++ 提交中击败了76.70%的用户
复杂度分析
时间复杂度：O(n)，其中 n 为数组的长度。利用单调栈求出每个元素为最小值的子序列长度需要的时间为 O(n)。
空间复杂度：O(n)。其中 n 为数组的长度。需要存储每个元素为结尾的子序列最小值之和，所需的空间为 O(n)。
author：
LeetCode-Solution