795. 区间子数组个数

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/comments/
Star
给你一个整数数组 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

滑动窗口

思路
容易求的是 最大值不超过 k 的子数组数量，而在某个范围内的不太好求，所以转化为求：
最大值不超过 right的子数组数量 - 最大值不超过left-1的子数组数量。
因为只用到了窗口最大元素，所以不需要有序列表。
窗口的大小由 right 和 left 来约束，然后 向右扩张窗口，如果当前 右端的元素大于 了 k， 那么直接将 窗口左端点收缩到 right即可
 
题解
class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        return self.helper(nums, right) - self.helper(nums, left-1)
    
    def helper(self, nums, k):
        """
        最大值不超过 k 的子数组个数
        """
        res = 0
        l, r = 0, 0
        while r < len(nums):
            cur_val = nums[r]
            r += 1
            # 此处窗口收缩一步到位！
            if cur_val > k:
                l = r

            res += r - l

        return res

滑动窗口 技巧

思路
遍历 数组，当超过 right时，窗口两指针都跳到当前数字后面，否则当大于等于 left 时候， 当前元素作为新来元素 可以和当前窗口中的其他数字 组成 子数组，个数 为 r -l+1
题解
class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
       
        l, r = 0, 0
        res = 0
        temp = 0
        while r < len(nums):
            if nums[r] > right:
                temp = 0
                l = r + 1
            elif nums[r] >= left:
                temp = r-l+1
            res += temp
            r += 1

        return res