给定数组nums[n],子数组的范围指子数组中最大元素与最小元素的差值,返回nums中所有子数组的范围之和。子数组是数组的连续非空序列。
1<=n<=1000; -1e9<=nums[i]<=1e9
分别考虑每个元素作为最小和最大值的情况,统计作为最小值的次数,作为最大值的次数,这个可以用单调栈求出,然后统计各位置对答案的贡献。由于数组中可能存在相同元素,为了避免重复统计,使用左闭右开区间。
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
vector<int> Min(n), Max(n);
auto getCnt = [&](int isMin, vector<int> &ret) {
vector<int> L(n), R(n);
vector<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && (isMin ? nums[s.back()] >= nums[i] : nums[s.back()] <= nums[i]))
s.pop_back();
L[i] = s.empty() ? -1 : s.back();
s.push_back(i);
}
s.clear();
for (int i = n-1; i >= 0; i--) {
while (!s.empty() && (isMin ? nums[i] < nums[s.back()] : nums[i] > nums[s.back()]))
s.pop_back();
R[i] = s.empty() ? n : s.back();
s.push_back(i);
}
for (int i = 0; i < n; i++) {
ret[i] = 1LL * (i-L[i]) * (R[i]-i);
}
};
getCnt(1, Min);
getCnt(0, Max);
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += 1LL * nums[i] * (Max[i] - Min[i]);
}
return ans;
}
};
标签:lc2104,nums,int,back,long,vector,数组,范围
From: https://www.cnblogs.com/chenfy27/p/18078332