https://leetcode.com/problems/sum-of-subarray-minimums/
the number of subarray starting with
and
这个过程可以简化为使用一个栈。对于被某个数从栈中弹出的数而言，它右侧第一个比它小的数就是这个数。所以我们可以对所有被弹出的数得到左侧的区间范围和右侧的区间范围。我觉得这是一种非常聪明的做法
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170776/Python-Simple-Stack-O(n)-Solution-10-lines
X. Monotone stack + DP
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170769/Java-O(n)-monotone-stack-with-DP
X.
Solution 1: Brute Force
Time complexity: O(n^2)
http://blog.leanote.com/post/edlinlink@qq.com/907
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.
https://zxi.mytechroad.com/blog/stack/leetcode-907-sum-of-subarray-minimums/
Time complexity: O(n)
Space complexity: O(n)
We can use a monotonic stack to compute left[i] and right[i] similar to 花花酱 LeetCode 901. Online Stock Span
- order matters, unlike 花花酱 LeetCode 898. Bitwise ORs of Subarrays we can not sort the numbers in this problem.
- e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].
- For A[i], assuming there are L numbers that are greater than A[i] in range A[0] ~ A[i – 1], and there are R numbers that are greater or equal than A[i] in the range of A[i+1] ~ A[n – 1]. Thus A[i] will be the min of (L + 1) * (R + 1) subsequences.
- e.g. A = [3,1,2,4], A[1] = 1, L = 1, R = 2, there are (1 + 1) * (2 + 1) = 6 subsequences are 1 is the min number. [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4]
Time complexity: O(n)
Space complexity: O(n)
We can use a monotonic stack to compute left[i] and right[i] similar to 花花酱 LeetCode 901. Online Stock Span
public int sumSubarrayMins(int[] A) {
final int kMod = 1000000007;
final int n = A.length;
Stack<Integer> nums = new Stack<>();
Stack<Integer> lens = new Stack<>();
int[] left = new int[n];
int[] right = new int[n];
int ans = 0;
for (int i = 0; i < n; ++i) {
int len = 1;
while (!nums.empty() && nums.peek() > A[i]) {
len += lens.pop(); nums.pop();
}
nums.push(A[i]);
lens.push(len);
left[i] = len;
}
nums.clear();
lens.clear();
for (int i = n - 1; i >= 0; --i) {
int len = 1;
while (!nums.empty() && nums.peek() >= A[i]) {
len += lens.pop(); nums.pop();
}
nums.push(A[i]);
lens.push(len);
right[i] = len;
}
for (int i = 0; i < n; ++i)
ans = (int)(ans + (long)A[i] * left[i] * right[i]) % kMod;
return ans;
}
实际上是要求
为了得到
所以这个问题在于求
举例，对于
那么，解释一下为什么
他是为了解决数组中有相等的数的情况。
假设有数组
所以在
算法
那么怎么求得
答案主要有两种做法，一种是用栈，一种是用数组。
解决方案1：栈
[C++/Java/Python] O(1)
就是用increasing stack来解决问题。
解决方案2：数组
5ms O(n) Java solution explained (beats 96%)
本来遍历要一个一个遍历的，像这样：
res = sum(A[i] * f(i))，其中f(i)是子数组的数量，A[i]是最小值。为了得到
f(i)，我们要得到-
left[i]，能在A[i]左侧取得的最长宽度，使得在这个范围内A[i]是最小值,且都大于A[i] -
right[i], 能在A[i]右侧取得的最长宽度，使得在这个范围内A[i]是最小值，且都大于等于A[i]
-
A[i]左侧有left[i] + 1种连续子数组的取法 -
A[i]右侧有right[i] + 1种连续子数组的取法
f(i) = (left[i] + 1) * (right[i] + 1)即可求得f(i)所以这个问题在于求
left[i]和right[i]举例，对于
[3,1,2,4]：left + 1 = [1,2,1,1]right + 1 = [1,3,2,1]f = [1,6,2,1]res = 3 * 1 + 1 * 6 + 2 * 2 + 4 * 1 = 17那么，解释一下为什么
left[i]要取大于A[i]，而right[i]只需要取大于等于A[i]：他是为了解决数组中有相等的数的情况。
假设有数组
...a1...a2...a3... ...an...其中，a1=a2=a3=...=an，那么这个连续数组的各种组合中，起点可以起自...a1, ...a2, ...a3，直到...an，而终点则可以尽可能地往右边取。所以在
i=a1处，left[i]最多取到a1，而在i=a2处，left[i]最少也取到a1+1。如此类推，起点可以从...a1...a2一直取到an，而终点可以从起点一直取到最右侧（只要大于等于起点的值），如此可以把全部的连续子数组的情况覆盖。算法
那么怎么求得
left[i]和right[i]呢？我们可以看以下两个同类型的问题的讨论:答案主要有两种做法，一种是用栈，一种是用数组。
解决方案1：栈
[C++/Java/Python] O(1)
就是用increasing stack来解决问题。
解决方案2：数组
5ms O(n) Java solution explained (beats 96%)
本来遍历要一个一个遍历的，像这样：
for (int i = 1; i < height.length; i++) {
int p = i - 1;
while (p >= 0 && height[p] >= height[i]) {
p--;
}
lessFromLeft[i] = p;
}
while (p >= 0 && height[p] >= height[i]) {
p = lessFromLeft[p];
}
Approach 2: Maintain Stack of Minimums
For a specific
j, let's try to count the minimum of each subarray [i, j]. The intuition is that as we increment j++, these minimums may be related to each other. Indeed, min(A[i:j+1]) = min(A[i:j], A[j]).
Playing with some array like
A = [1,7,5,2,4,3,9], with j = 6 the minimum of each subarray [i, j]is B = [1,2,2,2,3,3,9]. We can see that there are critical points i = 0, i = 3, i = 5, i = 6where a minimum is reached for the first time when walking left from j.
Algorithm
Let's try to maintain an RLE (run length encoding) of these critical points
B. More specifically, for the above (A, j), we will maintain stack = [(val=1, count=1), (val=2, count=3), (val=3, count=2), (val=9, count=1)], that represents a run length encoding of the subarray minimums B = [1,2,2,2,3,3,9]. For each j, we want sum(B).
As we increment
j, we will have to update this stack to include the newest element (val=x, count=1). We need to pop off all values >= x before, as the minimum of the associated subarray [i, j] will now be A[j] instead of what it was before.
At the end, the answer is the dot product of this stack: , which we also maintain on the side as the variable
dot.
public int sumSubarrayMins(int[] A) {
int MOD = 1_000_000_007;
Stack<RepInteger> stack = new Stack();
int ans = 0, dot = 0;
for (int j = 0; j < A.length; ++j) {
// Add all answers for subarrays [i, j], i <= j
int count = 1;
while (!stack.isEmpty() && stack.peek().val >= A[j]) {
RepInteger node = stack.pop();
count += node.count;
dot -= node.val * node.count;
}
stack.push(new RepInteger(A[j], count));
dot += A[j] * count;
ans += dot;
ans %= MOD;
}
return ans;
}
}
class RepInteger {
int val, count;
RepInteger(int v, int c) {
val = v;
count = c;
}
}
I guess this is a general intuition for most solution.
where
in which
res = sum(A[i] * f(i))where
f(i) is the number of subarrays,in which
A[i] is the minimum.
To get
f(i), we need to find out:left[i], the length of strict bigger numbers on the left of A[i],right[i], the length of bigger numbers on the right of A[i].
Then,
the number of subarray ending with
and
left[i] + 1 equals tothe number of subarray ending with
A[i],and
A[i] is single minimum.right[i] + 1 equals tothe number of subarray starting with
A[i],and
A[i] is the first minimum.
Finally
f(i) = (left[i] + 1) * (right[i] + 1)
For
[3,1,2,4] as example:left + 1 = [1,2,1,1]right + 1 = [1,3,2,1]f = [1,6,2,1]res = 3 * 1 + 1 * 6 + 2 * 2 + 4 * 1 = 17Explanation:
To calculate
we use two increasing stacks.
left[i] and right[i],we use two increasing stacks.
It will be easy if you can refer to this problem and my post:
901. Online Stock Span
I copy some of my codes from this solution.
901. Online Stock Span
I copy some of my codes from this solution.
More:
Complexity:
All elements will be pushed twice and popped at most twice
O(N) time, O(N) space public int sumSubarrayMins(int[] A) {
int res = 0, n = A.length, mod = (int)1e9 + 7;
int[] left = new int[n], right = new int[n];
Stack<int[]> s1 = new Stack<>(), s2 = new Stack<>();
for (int i = 0; i < n; ++i) {
int count = 1;
while (!s1.isEmpty() && s1.peek()[0] > A[i])
count += s1.pop()[1];
s1.push(new int[] {A[i], count});
left[i] = count;
}
for (int i = n - 1; i >= 0; --i) {
int count = 1;
while (!s2.isEmpty() && s2.peek()[0] >= A[i])
count += s2.pop()[1];
s2.push(new int[] {A[i], count});
right[i] = count;
}
for (int i = 0; i < n; ++i)
res = (res + A[i] * left[i] * right[i]) % mod;
return res;
}
int sumSubarrayMins(vector<int>& A) { stack<pair<int, int>> leftStack, rightStack; int n = A.size(); int left[n], right[n]; leftStack.emplace(-1, -1); // val, idx for (int i = 0; i < n; i++) { while (!leftStack.empty() && leftStack.top().first >= A[i]) leftStack.pop(); if (leftStack.top().second == -1) left[i] = i; else left[i] = i - leftStack.top().second - 1; leftStack.emplace(A[i], i); } rightStack.emplace(-1, -1); for (int i = n - 1; i >= 0; i--) { // 对于leftStack，此处写的是>= // 这意味着对于同一子序列中有多个最小元素的情况， // 我们选择把这种情况的值最右侧的最小元素中计算。 // （防止重复计算） while (!rightStack.empty() && rightStack.top().first > A[i]) rightStack.pop(); if (rightStack.top().second == -1) right[i] = n - i - 1; else right[i] = rightStack.top().second - i - 1; rightStack.emplace(A[i], i); } long long int sum = 0; for (int i = 0; i < n; i++) { sum += (left[i] + 1) * (right[i] + 1) * (long long int) A[i] % 1000000007; sum %= 1000000007; } return sum; }
显然一种较好的思路是，对于
A中的每一个值A[i]，寻找以它为最小值的子序列的数量。也就是说，我们需要寻找A[i]左侧第一个比它大的值的位置，以及右侧第一个比它大的值的位置。然后就可以计算对应的子序列的数量了。
1.Here I record
We can also only record index.
2. For left part and right part, the logic is same.
So for each, I used one stack and one pass.
This process can be optimized to one pass using one stack in total.
(A[i], count) in the stack.We can also only record index.
2. For left part and right part, the logic is same.
So for each, I used one stack and one pass.
This process can be optimized to one pass using one stack in total.
public int sumSubarrayMins(int[] A) {
Stack<Integer> s = new Stack<>();
int n = A.length, res = 0, mod = (int)1e9 + 7, j,k;
for (int i = 0; i <= n; i++) {
while (!s.isEmpty() && A[stack.peek()] > (i == n ? 0 : A[i])) {
j = stack.pop();
k = stack.isEmpty() ? -1 : stack.peek();
res = (res + A[j] * (i - j) * (j - k)) % mod;
}
stack.push(i);
}
return res;
}
Let's try to count the number of subarrays
#(j) for which A[j] is the right-most minimum. Then, the answer will be sum #(j) * A[j]. (We must say right-most so that we form disjoint sets of subarrays and do not double count any, as the minimum of an array may not be unique.)
This in turn brings us the question of knowing the smallest index
i <= j for which A[i], A[i+1], ..., A[j] are all <= A[j]; and the largest index k >= j for which A[j+1], A[j+2], ..., A[k] are all < A[j].
Algorithm
For example, if
A = [10, 3, 4, 5, _3_, 2, 3, 10] and we would like to know #(j = 4) [the count of the second 3, which is marked], we would find i = 1 and k = 5.
From there, the actual count is
#(j) = (j - i + 1) * (k - j + 1), as there are j - i + 1 choices i, i+1, ..., j for the left index of the subarray, and k - j + 1 choices j, j+1, ..., k for the right index of the subarray.
Answering these queries (ie. determining
(i, k) given j) is a classic problem that can be answered with a stack. We'll focus on the problem of finding i: the problem of finding k is similar.
Making a Prev Array
The idea is to maintain
stack, a monotone decreasing subsequence of A (actually, indices of A in implementation). These represent candidate boundaries i* - 1 for the next query, stored in increasing order of A[i*].
Now considering
j in increasing order, we can remove candidates for which A[i*] <= A[j] in decreasing order of i*.
For example, if
A = [10, 5, 3, 7, 0, 4, 5, 2, 1, _8_], then when considering j = 9 (A[j] = 8), we have a stack of boundaries like [-1, 0, 3, 6] (representing A[i*] = -inf, 10, 7, 5). We pop 6 and 3 from the stack, as 5 <= 8 and 7 <= 8, and we get the answer boundary i* - 1 = 0.
Note that this process is linear, since we do a linear amount of pushes and pops of the stack in total.
This is quite difficult to figure out, but this type of technique occurs often in many other problems, so it is worth learning in detail.
public int sumSubarrayMins(int[] A) {
int MOD = 1_000_000_007;
int N = A.length;
// prev has i* - 1 in increasing order of A[i* - 1]
// where i* is the answer to query j
Stack<Integer> stack = new Stack();
int[] prev = new int[N];
for (int i = 0; i < N; ++i) {
while (!stack.isEmpty() && A[i] <= A[stack.peek()])
stack.pop();
prev[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
// next has k* + 1 in increasing order of A[k* + 1]
// where k* is the answer to query j
stack = new Stack();
int[] next = new int[N];
for (int k = N-1; k >= 0; --k) {
while (!stack.isEmpty() && A[k] < A[stack.peek()])
stack.pop();
next[k] = stack.isEmpty() ? N : stack.peek();
stack.push(k);
}
// Use prev/next array to count answer
long ans = 0;
for (int i = 0; i < N; ++i) {
ans += (i - prev[i]) * (next[i] - i) % MOD * A[i] % MOD;
ans %= MOD;
}
return (int) ans;
}
What is monotonous increase stack?
Roughly speaking, the elements in the an monotonous increase stack keeps an increasing order.
The typical paradigm for monotonous increase stack:
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && in_stk.top() > A[i]){
in_stk.pop();
}
in_stk.push(A[i]);
}
What can monotonous increase stack do?
(1) find the previous less element of each element in a vector with O(n) time:
- What is the previous less element of an element?
For example:
[3, 7, 8, 4]
The previous less element of 7 is 3.
The previous less element of 8 is 7.
The previous less element of 4 is 3.
There is no previous less element for 3.
For simplicity of notation, we use abbreviation PLE to denote Previous Less Element.
- C++ code (by slitghly modifying the paradigm):
Instead of directly pushing the element itself, here for simplicity, we push the index.
We do some record when the index is pushed into the stack.
// previous_less[i] = j means A[j] is the previous less element of A[i].
// previous_less[i] = -1 means there is no previous less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
in_stk.pop();
}
previous_less[i] = in_stk.empty()? -1: in_stk.top();
in_stk.push(i);
}
(2) find the next less element of each element in a vector with O(n) time:
- What is the next less element of an element?
For example:
[3, 7, 8, 4]
The next less element of 8 is 4.
The next less element of 7 is 4.
There is no next less element for 3 and 4.
For simplicity of notation, we use abbreviation NLE to denote Next Less Element.
- C++ code (by slighly modifying the paradigm):
We do some record when the index is poped out from the stack.
// next_less[i] = j means A[j] is the next less element of A[i].
// next_less[i] = -1 means there is no next less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
auto x = in_stk.top(); in_stk.pop();
next_less[x] = i;
}
in_stk.push(i);
}
How can the monotonous increase stack be applied to this problem?
For example:Consider the element 3 in the following vector:
[2, 9, 7, 8, 3, 4, 6, 1]
| |
the previous less the next less
element of 3 element of 3
After finding both NLE and PLE of 3, we can determine the
distance between 3 and 2(previous less) , and the distance between 3 and 1(next less).
In this example, the distance is 4 and 3 respectively.
How much the element 3 contributes to the final answer?
It is
What is the final answer?
Denote by
Denote by
It is
3*(4*3).What is the final answer?
Denote by
left[i] the distance between element A[i] and its PLE.Denote by
right[i] the distance between element A[i] and its NLE.
The final answer is,
sum(A[i]*left[i]*right[i] )The last thing that needs to be mentioned for handling duplicate elements:
Method: Set strict less and non-strict less(less than or equal to) for finding NLE and PLE respectively. The order doesn't matter.
For example, the above code for finding NLE is strict less, while PLE is actually non-strict less.
Remark: Although in both loop conditions the signs are set as
>, for NLE, we make records inside the loop, while for PLE, records are done outside the loop.- What can monotonous decrease stack do?
- Some applications of monotone (increase/decrease) stack in leetcode:
Next Greater Element II (a very basic one)
Largest Rectangle in Histogram(almost the same as this problem)
Maximal Rectangle(please do this problem after you solve the above one)
Trapping Rain Water (challenge)
Remove Duplicate Letters(challenge)
Remove K Digits
Create Maximum Number
132 Pattern(challenge, instead of focusing on the elements in the stack, this problem focuses on the elements poped from the monotone stack)
sliding window maximum(challenge, monotone queue)
Max Chunks To Make Sorted II
The solution (One pass)
int sumSubarrayMins(vector<int>& A) {
stack<pair<int, int>> in_stk_p, in_stk_n;
// left is for the distance to previous less element
// right is for the distance to next less element
vector<int> left(A.size()), right(A.size());
//initialize
for(int i = 0; i < A.size(); i++) left[i] = i + 1;
for(int i = 0; i < A.size(); i++) right[i] = A.size() - i;
for(int i = 0; i < A.size(); i++){
// for previous less
while(!in_stk_p.empty() && in_stk_p.top().first > A[i]) in_stk_p.pop();
left[i] = in_stk_p.empty()? i + 1: i - in_stk_p.top().second;
in_stk_p.push({A[i],i});
// for next less
while(!in_stk_n.empty() && in_stk_n.top().first > A[i]){
auto x = in_stk_n.top();in_stk_n.pop();
right[x.second] = i - x.second;
}
in_stk_n.push({A[i], i});
}
int ans = 0, mod = 1e9 +7;
for(int i = 0; i < A.size(); i++){
ans = (ans + A[i]*left[i]*right[i])%mod;
}
return ans;
}
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170776/Python-Simple-Stack-O(n)-Solution-10-lines
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170769/Java-O(n)-monotone-stack-with-DP
Solution 1: Brute Force
Time complexity: O(n^2)
public int sumSubarrayMins(int[] A) {
final int kMod = 1000000007;
final int n = A.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
int left = 0;
for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);
int right = 0;
for (int j = i + 1; j < n && A[j] >= A[i]; ++j, ++right);
ans = (int)((ans + (long)A[i] * (left + 1) * (right + 1)) % kMod);
}
return ans;
}
http://blog.leanote.com/post/edlinlink@qq.com/907
