给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
示例 1:
输入:nums = [2,1,4,3], left = 2, right = 3
输出:3
解释:满足条件的三个子数组:[2], [2, 1], [3]
一个点的贡献值为其作为最大值的左边界和右边界 对应的所有子数组的乘积
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
模拟 确实妙
// int n = nums.size();
// int ans = 0, m0 = -1, m1 = -1;
// for(int i = 0; i < n; i ++){
// if(nums[i] > right) m0 = i;
// if(nums[i] >= left) m1 = i;
// ans += m1 - m0;
// }
// return ans;
stack<int> stk;
int n = nums.size();
vector<int> l(n, -1), r(n, n);
for(int i = 0; i < n; i ++){
while(stk.size() && nums[stk.top()] <= nums[i]) stk.pop();
if(stk.size()) l[i] = stk.top();
stk.push(i);
}
while(stk.size()) stk.pop();
for(int i = n - 1; i >= 0; i --){
while(stk.size() && nums[stk.top()] < nums[i]) stk.pop();
if(stk.size()) r[i] = stk.top();
stk.push(i);
}
int ans = 0;
for(int i = 0; i < n; i ++){
if(nums[i] >= left && nums[i] <= right)
ans += (i - l[i]) * (r[i] - i);
}
return ans;
}
};