# 907. Sum of Subarray Minimums

Given an array of integers `A`, find the sum of `min(B)`, where `B` ranges over every (contiguous) subarray of `A`.

Since the answer may be large, return the answer modulo `10^9 + 7`.

Example 1:

``````Input: [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.
``````

Note:

1. `1 <= A.length <= 30000`
2. `1 <= A[i] <= 30000`

``````class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
int res = A[0], n = A.size(), M = 1e9 + 7;
vector<int> dp(n);
dp[0] = A[0];
for (int i = 1; i < n; ++i) {
if (A[i] >= A[i - 1]) dp[i] = dp[i - 1] + A[i];
else {
int j = i - 1;
while (j >= 0 && A[i] < A[j]) --j;
dp[i] = (j < 0) ? (i + 1) * A[i] : (dp[j] + (i - j) * A[i]);
}
res = (res + dp[i]) % M;
}
return res;
}
};
``````

``````class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
int res = 0, n = A.size(), M = 1e9 + 7;
stack<int> st{{-1}};
vector<int> dp(n + 1);
for (int i = 0; i < n; ++i) {
while (st.top() != -1 && A[i] <= A[st.top()]) {
st.pop();
}
dp[i + 1] = (dp[st.top() + 1] + (i - st.top()) * A[i]) % M;
st.push(i);
res = (res + dp[i + 1]) % M;
}
return res;
}
};
``````

``````class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
int res = 0, n = A.size(), M = 1e9 + 7;
stack<pair<int, int>> st_pre, st_next;
vector<int> left(n), right(n);
for (int i = 0; i < n; ++i) {
while (!st_pre.empty() && st_pre.top().first > A[i]) {
st_pre.pop();
}
left[i] = st_pre.empty() ? (i + 1) : (i - st_pre.top().second);
st_pre.push({A[i], i});
right[i] = n - i;
while (!st_next.empty() && st_next.top().first > A[i]) {
auto t = st_next.top(); st_next.pop();
right[t.second] = i - t.second;
}
st_next.push({A[i], i});
}
for (int i = 0; i < n; ++i) {
res = (res + A[i] * left[i] * right[i]) % M;
}
return res;
}
};
``````

``````class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
int res = 0, n = A.size(), M = 1e9 + 7;
stack<int> st;
for (int i = 0; i <= n; ++i) {
int cur = (i == n) ? 0 : A[i];
while (!st.empty() && cur < A[st.top()]) {
int idx = st.top(); st.pop();
int left = idx - (st.empty() ? -1 : st.top());
int right = i - idx;
res = (res + A[idx] * left * right) % M;
}
st.push(i);
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/907

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.

https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170769/Java-O(n)-monotone-stack-with-DP

https://leetcode.com/problems/sum-of-subarray-minimums/discuss/178876/stack-solution-with-very-detailed-explanation-step-by-step

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation