LeetCode_区间问题_中等_795.区间子数组个数

1.题目

给你一个整数数组 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⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum

2.思路

（1）计数
思路参考本题官方题解。

① 设函数 count(int[] nums, int bound) 用于计算数组 nums 中所有元素都小于等于 bound 的子数组数量。
② 那么 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组数量就等于 count(nums, right) - count(nums, left - 1)。

3.代码实现（Java）

//思路1————计数
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }
    
    //count(nums, bound)计算数组 nums 中所有元素都小于等于 bound 的子数组数量
    private int count(int[] nums, int bound) {
        int res = 0;
        int cur = 0;
        for (int num : nums) {
            cur = (num <= bound) ? cur + 1 : 0;
            res += cur;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17