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

本是古典何须时尚 2023-10-06 23:43 10阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 <= 105  
0 <= nums\[i\] <= 109  
0 <= left <= right <= 109

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

## 2.思路 ##

（1）计数  
思路参考[本题官方题解][Link 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/solution/qu-jian-zi-shu-zu-ge-shu-by-leetcode/