问题描述
795. 区间子数组个数 (Medium)
给你一个整数数组 nums 和两个整数： left 及 right 。找
出 nums 中连续、非空且其中最大元素在范围 [left, right]
内的子数组，并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
示例 1：
输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]
示例 2：
输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7
提示：
1 <= nums.length <= 10⁵0 <= nums[i] <= 10⁹0 <= left <= right <= 10⁹
解题思路
单调栈
当我们看到这种连续区间中的最大值的题目时，就可以考虑使用单调栈。
对 nums[idx]，我们需要找到以 nums[idx] 为最大值的子数组的数量，设 lidx 为满足 nums[l] >= nums[idx] 且 l < idx 的最大的 l；设 ridx 为满足 nums[r] > nums[idx] 且 r > idx 中的最小的 r。我们要做的就是枚举满足 0 <= idx < n 的所有的 idx，找到对应的 lidx 和 ridx，从而计算出子数组的数量。
子数组的数量为
(ridx - idx) * (idx - lidx)
在本题中，我们可以考虑使用从栈底到栈顶单调递减的栈，来求出 ridx 和 lidx。注意，栈中的元素是索引 idx。枚举 i，当 nums[i] > nums[stk.top()] 时，对 idx = stk.top()，将栈顶元素出栈，ridx = i，lidx 为新栈顶，如果栈为空，则 lidx = -1。
当枚举完 i 之后，对栈中剩余元素，idx = stk.top(), ridx = n，将栈中元素出栈，如果栈为空，lidx = -1，否则 lidx = stk.top();。
双指针
代码
单调栈
class Solution {
public:
int numSubarrayBoundedMax(vector<int> &nums, int left, int right) {
// 单调栈，以 nums[i] 为最大值的子数组的个数
// 栈底到栈顶单调递减
int res = 0;
stack<int> stk;
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (!stk.empty() && nums[i] > nums[stk.top()]) {
int idx = stk.top();
int len1 = i - idx;
int val = nums[idx];
stk.pop();
int len2 = stk.empty() ? idx + 1 : idx - stk.top();
if (val <= right && val >= left) {
res += len1 * len2;
}
}
stk.push(i);
}
while (!stk.empty()) {
int idx = stk.top();
int len1 = n - idx;
int val = nums[idx];
stk.pop();
int len2 = stk.empty() ? idx + 1 : idx - stk.top();
if (val <= right && val >= left) {
res += len1 * len2;
}
}
return res;
}
};