2104. Sum of Subarray Ranges
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.
Return the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Constraints:
1 <= nums.length <= 1000
-10^9 <= nums[i] <= 10^9
Follow-up: Could you find a solution with O(n) time complexity?
Analysis:
First of all, we can use a two-layer for loop to solve this problem, since the maximum length is 10^3, so O(N^2) is acceptable for the online OJ.
For any array with N elements, there are N*(N+1)/2 sub-arrays. So we just need to get the min and max of each sub-array, and sum the diffs together.
See the code below:
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
long long res = 0, n = nums.size();
for(int i=0; i<n; ++i) {
int mx = nums[i], mi = mx;
for(int j=i+1; j<n; ++j) {
mx = max(nums[j], mx);
mi = min(nums[j], mi);
res += (long)mx - (long)mi;
}
}
return res;
}
};As asked in the follow up, can we do better?
(Please be noted: the following logic is quite non-intuitive, and requires at least 10 min to read.)
The answer is yes. For example, with a stack, the time complexity can be decreased to O(N).
Think about one classical question about stack: In an integer array with size of N, for each element, what is the first element larger than it?
One observation is that: if we maintain a monotonically increasing stack, then we can derive many useful information. For example, we can derive the answers to the above question for every elements in a time complexity of O(N), or just in one scan for every element.
At the same time, we can get the number of the elements larger than every element on its right side continuously!
For example, say we have one array [6, 9, 3, 5, 10, 1, 4, 7], and we will use a stack to scan through the array from left to right.
One trick here is to use the index instead of value (recording index is obvious better than value with an array, since once we know the index, we know the value as well; but not the reverse)
At step 1, we have [0];
2, [0, 1]
At step 3, the index is 2 and the value is 3, and 3 < arr[1] == 9 (which is the top of the stack), we need to pop out the top element in the stack, so we get the number of elements larger than arr[1] continuously is (2 - 1 - 1) = 1. So res[1] = 0;
We will continue the comparison between the new top of the stack and arr[2]. Now the top is 0. and arr[0] == 6 > arr[2] == 3, so we need to pop it as well. So res[0] = 2 - 0 - 1= 1.
The stack becomes empty, so we just put 2 into it.
So far, we have obtained res[0] = 1 and res[1] = 0. Are they correct?
It is straightforward that the answer is yes. For arr[0], there is one which is arr[1]; for arr[1], there is none.
Let continue the scan.
At step 4, index = 3, we have [2, 3];
5, 4, [2, 3, 4];
At step 6, 5, and we need to pop out elements again, since arr[5] < top of the stack
In this way, we can get all answers for every elements in a single scan!
The take-home message here is:
With a stack, we can get the number of the elements larger than every element on its right side continuously in one single scan!
Similarly, if we change the scanning direction, we can get the number of the elements larger than every element on its left side continuously in one scan as well.
After having these two values, we can calculate the number of sub-arrays with the current element as the minimum.
If the larger elements on the right side continuously is fr[i] and on the left side continuously is fl[i], then there are (fr[i] + 1) * (fl[i] + 1) sub-arrays with arr[i] as the minimum.
One corner case is when the array have elements with the same values. For example, the array is [5, 5, 5]. In this case, we can use a tiny trick: on the right side, we can calculate the number of elements no-smaller than the current element continuously; on the left side, we just calculate the number of elements strictly larger than the current element continuously.
For the [5, 5, 5] array, the fr array is [2, 1, 0], the fl array is [0, 0, 0].
So the number of the subarray with arr[0] as the minimum is: (2+1)*(0+1) = 3;
So the number of the subarray with arr[1] as the minimum is: (1+1)*(0+1) = 2;
So the number of the subarray with arr[2] as the minimum is: (0+1)*(0+1) = 1;
Similarly, we can count the number of the subarray with arr[i] as the maximum in O(N) as well (with a monotonically decreasing stack).
Once we figure out the frequency of the maximum elements and minimum elements, we can calculate the difference of all of them. (The order does not matter. Or we do not need to figure out the maximum and minimum of each subarray).
See the code below:
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
long long res = 0;
int n = nums.size();
stack<int> sk1;
vector<int> dp1(n, 0), dp2(n, 0), dp3(n, 0), dp4(n, 0);
for(int i=0; i<n; ++i) {
while(sk1.size() && nums[sk1.top()] > nums[i]) {
int id = sk1.top();
sk1.pop();
dp1[id] = i - id;
}
sk1.push(i);
}
while(sk1.size()) {
int id = sk1.top();
sk1.pop();
dp1[id] = n - id;
}
for(int i=n-1; i>=0; --i) {
while(sk1.size() && nums[sk1.top()] >= nums[i]) {
int id = sk1.top();
sk1.pop();
dp2[id] = id - i;
}
sk1.push(i);
}
while(sk1.size()) {
int id = sk1.top();
sk1.pop();
dp2[id] = id + 1;
}
for(int i=0; i<n; ++i) {
while(sk1.size() && nums[sk1.top()] < nums[i]) {
int id = sk1.top();
sk1.pop();
dp3[id] = i - id;
}
sk1.push(i);
}
while(sk1.size()) {
int id = sk1.top();
sk1.pop();
dp3[id] = n - id;
}
for(int i=n-1; i>=0; --i) {
while(sk1.size() && nums[sk1.top()] <= nums[i]) {
int id = sk1.top();
sk1.pop();
dp4[id] = id - i;
}
sk1.push(i);
}
while(sk1.size()) {
int id = sk1.top();
sk1.pop();
dp4[id] = id + 1;
}
for(int i=0; i<n; ++i) {
// cout<<dp1[i]<<" "<<dp2[i]<<" "<<dp3[i]<<" "<<dp4[i]<<endl;
res += (long)nums[i] * ((dp3[i]) * (dp4[i]) - (dp1[i]) * (dp2[i]));
}
return res;
}
};We can make the code much more concise.
With a monotonically non-decreasing stack, when we pop out one element, we can calculate the number of (strictly) larger elements on the left side continuously as well. To get this, we just need to compare the index popped out with the current top of the stack, or left boundary if stack if empty. (Why?)
See the code below:
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
long long res = 0, n = nums.size();
stack<int> sk;
for(int i=0; i<=n; ++i) {
while(sk.size() && (i==n || nums[sk.top()] > nums[i])) {
int id = sk.top();
sk.pop();
int fr = i - id;
int fl = sk.empty() ? id + 1 : id - sk.top();
res -= (long long)nums[id]*fr*fl;
}
if(i<n) sk.push(i);
}
for(int i=0; i<=n; ++i) {
while(sk.size() && (i==n || nums[sk.top()] < nums[i])) {
int id = sk.top();
sk.pop();
int fr = i - id;
int fl = sk.empty() ? id + 1 : id - sk.top();
res += (long long)nums[id]*fr*fl;
}
if(i<n) sk.push(i);
}
return res;
}
};
No comments:
Post a Comment