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

问题描述

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;
    }
};