# 795.区间子数组个数 (Medium)

## 问题描述
[795. 区间子数组个数 (Medium)](https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/)
给你一个整数数组 `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();`。

### 双指针


## 代码
### 单调栈
```cpp
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;
    }
};
```