907. Sum of Subarray Minimums
Đề Bài
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 * 1041 <= arr[i] <= 3 * 104
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0907-sum-of-subarray-minimums.cpp
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
arr.insert(arr.begin(), 0);
stack<int> st;
st.push(0);
int n = arr.size();
vector<int> dp(n, 0);
const int mod = 1e9 + 7;
for (int i = 1; i < n; ++i) {
while (!st.empty() and arr[st.top()] > arr[i]) {
st.pop();
}
int j = st.top();
dp[i] = dp[j] + (i - j) * arr[i];
st.push(i);
}
int res = 0;
for (int i = 1; i < n; ++i) {
res = (res + dp[i]) % mod;
}
return res;
}
};