[LeetCode] 907. Sum of Subarray Minimums
grandyang opened this issue · 0 comments
Given an array of integers arr, find the sum of min(b)
, where b
ranges over every (contiguous) subarray of arr
. Since the answer may be large, return the answer modulo 109 + 7
.
Example 1:
Input: arr = [3,1,2,4]
Output: 17
Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.
Example 2:
Input: arr = [11,81,94,43,3]
Output: 444
Constraints:
1 <= arr.length <= 3 * 104
1 <= arr[i] <= 3 * 104
这道题给了一个数组,对于所有的子数组,找到最小值,并返回累加结果,并对一个超大数取余。由于我们只关心子数组中的最小值,所以对于数组中的任意一个数字,需要知道其是多少个子数组的最小值。就拿题目中的例子 [3,1,2,4] 来分析,开始遍历到3的时候,其本身就是一个子数组,最小值也是其本身,累加到结果 res 中,此时 res=3,然后看下个数1,是小于3的,此时新产生了两个子数组 [1] 和 [3,1],且最小值都是1,此时在结果中就累加了 2,此时 res=5。接下来的数字是2,大于之前的1,此时会新产生三个子数组,其本身单独会产生一个子数组 [2],可以先把这个2累加到结果 res 中,然后就是 [1,2] 和 [3,1,2],可以发现新产生的这两个子数组的最小值还是1,跟之前计算数字1的时候一样,可以直接将以1结尾的子数组最小值之和加起来,那么以2结尾的子数组最小值之和就是 2+2=4,此时 res=9。对于最后一个数字4,其单独产生一个子数组 [4],还会再产生三个子数组 [3,1,2,4], [1,2,4], [2,4],其并不会对子数组的最小值产生影响,所以直接加上以2结尾的子数组最小值之和,总共就是 4+4=8,最终 res=17。
分析到这里,就知道我们其实关心的是以某个数字结尾时的子数组最小值之和,可以用一个一维数组 dp,其中 dp[i] 表示以数字 arr[i] 结尾的所有子数组最小值之和,将 dp[0] 初始化为 arr[0],结果 res 也初始化为 arr[0]。然后从第二个数字开始遍历,若大于等于前一个数字,则当前 dp[i] 赋值为 dp[i-1]+arr[i],前面的分析已经解释了,当前数字 arr[i] 组成了新的子数组,同时由于 arr[i] 不会影响最小值,所以要把之前的最小值之和再加一遍。假如小于前一个数字,就需要向前遍历,去找到第一个小于 arr[i] 的位置j,假如j小于0,表示前面所有的数字都是小于 arr[i] 的,那么 arr[i] 是前面 i+1 个以 arr[i] 结尾的子数组的最小值,累加和为 (i+1) x arr[i],若j大于等于0,则需要分成两部分累加,dp[j] + (i-j)xA[i],这个也不难理解,前面有 i-j 个以 arr[i] 为结尾的子数组的最小值是 arr[i],而再前面的子数组的最小值就不是 arr[i] 了,但是还是需要加上一遍其本身的最小值之和,因为每个子数组末尾都加上 arr[i] 均可以组成一个新的子数组,最终的结果 res 就是将 dp 数组累加起来即可,别忘了对超大数取余,参见代码如下(现在这种方法已经超时 TLE 了):
解法一:
// Time Limit Exceeded
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int res = arr[0], n = arr.size(), M = 1e9 + 7;
vector<int> dp(n);
dp[0] = arr[0];
for (int i = 1; i < n; ++i) {
if (arr[i] >= arr[i - 1]) dp[i] = dp[i - 1] + arr[i];
else {
int j = i - 1;
while (j >= 0 && arr[i] < arr[j]) --j;
dp[i] = (j < 0) ? (i + 1) * arr[i] : (dp[j] + (i - j) * arr[i]);
}
res = (res + dp[i]) % M;
}
return res;
}
};
上面的方法虽然 work,但不是很高效,原因是在向前找第一个小于当前的数字,每次都要线性遍历一遍,造成了平方级的时间复杂度。而找每个数字的前小数字或是后小数字,正是单调栈擅长的,可以参考博主之前的总结贴 LeetCode Monotonous Stack Summary 单调栈小结。这里我们用一个单调栈来保存之前一个小的数字的位置,栈里先提前放一个 -1,作用会在之后讲解。还是需要一个 dp 数组,跟上面的定义基本一样,但是为了避免数组越界,将长度初始化为 n+1,其中 dp[i] 表示以数字 arr[i-1] 结尾的所有子数组最小值之和。对数组进行遍历,当栈顶元素不是 -1 且 arr[i] 小于等于栈顶元素,则将栈顶元素移除。这样栈顶元素就是前面第一个比 arr[i] 小的数字,此时 dp[i+1] 更新还是跟之前一样,分为两个部分,由于知道了前面第一个小于 arr[i] 的数字位置,用当前位置减去栈顶元素位置再乘以 arr[i],就是以 arr[i] 为结尾且最小值为 arr[i] 的子数组的最小值之和,而栈顶元素之前的子数组就不受 arr[i] 影响了,直接将其 dp 值加上即可。将当前位置压入栈,并将 dp[i+1] 累加到结果 res,同时对超大值取余,参见代码如下:
解法二:
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int res = 0, n = arr.size(), M = 1e9 + 7;
stack<int> st{{-1}};
vector<int> dp(n + 1);
for (int i = 0; i < n; ++i) {
while (st.top() != -1 && arr[i] <= arr[st.top()]) {
st.pop();
}
dp[i + 1] = (dp[st.top() + 1] + (i - st.top()) * arr[i]) % M;
st.push(i);
res = (res + dp[i + 1]) % M;
}
return res;
}
};
再来看一种解法,由于对于每个数字,只要知道了其前面第一个小于其的数字位置,和后面第一个小于其的数字位置,就能知道当前数字是多少个子数组的最小值,直接相乘累加到结果 res 中即可。这里我们用两个单调栈 st_pre 和 st_next,栈里放一个数对儿,由数字和其在原数组的坐标组成。还需要两个一维数组 left 和 right,其中 left[i] 表示以 arr[i] 为结束为止且 arr[i] 是最小值的子数组的个数,right[i] 表示以 arr[i] 为起点且 arr[i] 是最小值的子数组的个数。对数组进行遍历,当 st_pre 不空,且栈顶元素大于 arr[i],移除栈顶元素,这样剩下的栈顶元素就是 arr[i] 左边第一个小于其的数字的位置,假如栈为空,说明左边的所有数字都小于 arr[i],则 left[i] 赋值为 i+1,否则赋值为用i减去栈顶元素在原数组中的位置的值,然后将 arr[i] 和i组成数对儿压入栈 st_pre。对于 right[i] 的处理也很类似,先将其初始化为 n-i,然后看若 st_next 不为空且栈顶元素大于 arr[i],然后取出栈顶元素t,由于栈顶元素t是大于 arr[i]的,所以 right[t.second] 就可以更新为 i-t.second,然后将 arr[i] 和i组成数对儿压入栈 st_next,最后再遍历一遍原数组,将每个 arr[i] x left[i] x right[i] 算出来累加起来即可,别忘了对超大数取余,参见代码如下:
解法三:
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int res = 0, n = arr.size(), M = 1e9 + 7;
stack<pair<int, int>> st_pre, st_next;
vector<long> left(n), right(n);
for (int i = 0; i < n; ++i) {
while (!st_pre.empty() && st_pre.top().first > arr[i]) {
st_pre.pop();
}
left[i] = st_pre.empty() ? (i + 1) : (i - st_pre.top().second);
st_pre.push({arr[i], i});
right[i] = n - i;
while (!st_next.empty() && st_next.top().first > arr[i]) {
auto t = st_next.top(); st_next.pop();
right[t.second] = i - t.second;
}
st_next.push({arr[i], i});
}
for (int i = 0; i < n; ++i) {
res = (res + arr[i] * left[i] * right[i]) % M;
}
return res;
}
};
我们也可以对上面的解法进行空间上的优化,只用一个单调栈,用来记录当前数字之前的第一个小的数字的位置,然后遍历每个数字,但是要多遍历一个数字,i从0遍历到n,当 i=n 时,cur 赋值为0,否则赋值为 arr[i]。然后判断若栈不为空,且 cur 小于栈顶元素,则取出栈顶元素位置 idx,由于是单调栈,那么新的栈顶元素就是 arr[idx] 前面第一个较小数的位置,由于此时栈可能为空,所以再去之前要判断一下,若为空,则返回 -1,否则返回栈顶元素,用 idx 减去栈顶元素就是以 arr[idx] 为结尾且最小值为 arr[idx] 的子数组的个数,然后用i减去 idx 就是以 arr[idx] 为起始且最小值为 arr[idx] 的子数组的个数,然后 arr[idx] x left x right 就是 arr[idx] 这个数字当子数组的最小值之和,累加到结果 res 中并对超大数取余即可,参见代码如下:
解法四:
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int res = 0, n = arr.size(), M = 1e9 + 7;
stack<int> st;
for (int i = 0; i <= n; ++i) {
int cur = (i == n) ? 0 : arr[i];
while (!st.empty() && cur < arr[st.top()]) {
int idx = st.top(); st.pop();
long left = idx - (st.empty() ? -1 : st.top());
long right = i - idx;
res = (res + arr[idx] * left * right) % M;
}
st.push(i);
}
return res;
}
};
Github 同步地址:
参考资料:
https://leetcode.com/problems/sum-of-subarray-minimums/
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170857/One-stack-solution
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/222895/Java-No-Stack-solution.