795. 区间子数组个数

给你一个整数数组 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^5
• 0 <= nums[i] <= 10^9
• 0 <= left <= right <= 10^9

作差

计算所有元素最大值小于等于 right 和 left - 1 的子数组数量，作差即可。

计算时遍历数组，如果当前元素小于等于 lower，更新当前子数组长度。cur表示以x结尾的数组的个数。如果当前元素大于 lower，重置当前子数组长度。累加符合条件的子数组数量。

类似前缀和思想。

假设nums=[2,1,4,3]，我们要找最大值小于等于3的子数组的数量。

2<=3，以2结尾的子数组：[2]

1<=3，以1结尾的子数组: [2,1], [1]

4>3，cur置为0

3<=3，以3结尾的子数组: [3]

res=1+2+0+1=4。

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        // 返回在区间 [left, right] 之间的子数组的数量
        // 通过计算两个边界内的子数组数量差值得到
        return count(nums, right) - count(nums, left - 1);
    }

    // 计算所有元素最大值小于等于 lower 的子数组数量
    public int count(int[] nums, int lower) {
        int res = 0; // 用于存储结果，即符合条件的子数组数量
        int cur = 0; // 当前连续子数组的长度

        // 遍历数组
        for (int x : nums) {
            if (x <= lower) {
                // 如果当前元素小于等于 lower，更新当前子数组长度。cur表示以x结尾的数组的个数。重点是连续。
                cur++;
            } else {
                // 如果当前元素大于 lower，重置当前子数组长度
                cur = 0;
            }
            // 本轮计算结束，累加符合条件的子数组数量。注意是累加。
            res += cur;
        }

        return res; // 返回结果
    }
}

• 时间复杂度： $O(n)$ ，其中 $n$ 是 $n u m s$ 的长度。整个求解过程需要遍历两次 $n u m s$ 。
• 空间复杂度: $O(1)$ 。只使用到常数个变量。