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.
- monotonic stack with two min max pointer for divide range
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public:
long long subArrayRanges(vector<int>& A) {
long long res = 0, n = A.size();
vector<pair<int, int>> mi, ma;
for(int i = 0; i < n; i++) {
int mii = i, mai = i;
while(!mi.empty() and mi.back().second >= A[i]) {
mii = mi.back().first; mi.pop_back();
}
while(!ma.empty() and ma.back().second <= A[i]) {
mai = ma.back().first; ma.pop_back();
}
mi.push_back({mii, A[i]});
ma.push_back({mai, A[i]});
int j = mi.size() - 1, k = ma.size() - 1, bound = i;
while(j >= 0 and k >= 0) {
auto [mii, miv] = mi[j];
auto [mai, mav] = ma[k];
int count = bound - max(mii, mai);
res += 1ll * count * (mav - miv);
if(mai == mii) {
j--; k--;
bound = mai;
} else if(mai > mii) {
bound = mai;
k--;
} else {
bound = mii;
j--;
}
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
long long helper(vector<int>& A, function<bool (int, int)> cmp) {
vector<int> st;
long long res = 0, n = A.size();
for(int i = 0; i <= n; i++) {
while(!st.empty() and (i == n or cmp(A[i], A[st.back()]))) {
int j = st.back(), k = st.size() >= 2 ? st[st.size() - 2] : -1;
res += 1ll * (i - j) * (j - k) * A[j];
st.pop_back();
}
st.push_back(i);
}
return res;
}
public:
long long subArrayRanges(vector<int>& A) {
return helper(A, greater<int>()) - helper(A, less<int>());
}
};
|
