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
Think from simple case to complex case.
If there is only one number, say A = [1], the answer is A[0] = 1.
If there are two numbers, can we reuse the previous results?
Assume based on A = [1], we add a number 2. This new number will create two new subarrays, [1,2] and [2]. The min value of [2] is trivial. For min value of [1,2], we can reuse the result we got when A = [1].
Now assume based on A = [1], we add a number 0. This new number will create two new subarrays, [1,0] and [0]. For [1,0], the min value becomes 0. And if we keep adding more numbers, this leading 1 will no longer be added because of this smaller 0.
Here we can see that we need a mono stack of keep track of the small numbers in ascending order. For example, if A = [100,1,100,2,100,3,100], the stack should be [1,2,3,100]. Then when we push a new number into the stack, we know that are the numbers that need to be replaced. Each time we pop a number, we
// OJ: https://leetcode.com/problems/sum-of-subarray-minimums/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
stack<int> q; // index
q.push(-1);
long N = A.size(), ans = 0, sum = 0, mod = 1e9+7;
for (int i = 0; i < N; ++i) {
sum = (sum + A[i]) % mod;
while (q.top() != -1 && A[q.top()] >= A[i]) {
int j = q.top();
q.pop();
int c = j - q.top();
sum = (sum + c * (A[i] - A[j]) % mod) % mod;
}
q.push(i);
ans = (ans + sum) % mod;
}
return ans;
}
};https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170750/C++JavaPython-Stack-Solution