LeetCode 795. 区间子数组个数
原题链接
中等
作者:
我是java同学
,
2023-10-12 08:43:22
,
所有人可见
,
阅读 64
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int n = nums.size();
stack<int> stk;
vector<int> l(n), r(n);
for (int i = 0; i < n; i ++ ) {
while (stk.size() && nums[stk.top()] <= nums[i]) stk.pop();
if (stk.empty()) l[i] = -1;
else l[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; i -- ) {
while (stk.size() && nums[stk.top()] < nums[i]) stk.pop();
if (stk.empty()) r[i] = n;
else r[i] = stk.top();
stk.push(i);
}
int res = 0;
for (int i = 0; i < n; i ++ )
if (nums[i] >= left && nums[i] <= right)
res += (i - l[i]) * (r[i] - i);
return res;
}
};