Solutions CS101

Appearance

2444.统计定界子数组的数目 ​

Sliding Window, Monotonic Queue, https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/

给你一个整数数组 nums 和两个整数 minK 以及 maxK 。

nums 的定界子数组是满足下述条件的一个子数组：

  • 子数组中的 最小值 等于 minK 。
  • 子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。

示例 2：

输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。

提示：

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i], minK, maxK <= 10^6

用线性遍历的方法来做，保持三个指针：

  • min_i：上一次出现 minK 的位置
  • max_i：上一次出现 maxK 的位置
  • bad_i：上一次出现不在 [minK, maxK] 范围内元素的位置

每次遍历时，如果当前位置的元素合法，就可以统计以当前位置为结尾的定界子数组数量。

完整代码：

python
from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        min_i = max_i = bad_i = -1
        ans = 0
        for i, num in enumerate(nums):
            if not (minK <= num <= maxK):
                bad_i = i
            if num == minK:
                min_i = i
            if num == maxK:
                max_i = i
            ans += max(0, min(min_i, max_i) - bad_i)
        return ans

简单解释一下这段代码的思路：

  • 如果当前位置之前有合法的 minK 和 maxK，并且中间没有出现不合法的数（即在 bad_i 之后），那么以当前位置结尾的子数组就可以贡献 min(min_i, max_i) - bad_i 个。
  • 取 min(min_i, max_i) 是因为我们要保证 minK 和 maxK 都出现了，取它们更早的那个位置。
  • 每次累加就可以得到总答案了。