点击获取AI摘要

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

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

问题分析

我们要统计所有「最小值＝minK 且最大值＝maxK」的子数组个数。核心在于：

无效区间：任何超出区间 $minK, maxK$ 的元素都会“破坏”子数组；我们记录它的最近位置 last_invalid，子数组一旦跨过此位置就一定包含不合格元素。
关键位置：必须同时出现 minK 和 maxK，因此我们分别记录扫描到当前位置为止，最后一次出现 minK 的下标 last_min，以及最后一次出现 maxK 的下标 last_max。
结尾贡献：对于每个位置 i，以它为结尾的所有合法子数组，起始位置 j 必须满足：
- j > last_invalid（子数组中不包含任何无效元素）
- 而且子数组要同时包含最近一次的 minK 和 maxK，也就是说 j ≤ min(last_min, last_max)。
因此，以 i 结尾的合法子数组数量是：
1
max(0, min(last_min, last_max) - last_invalid)
累加到全局答案中即可。

算法思路

定义三个指针/下标变量：
- last_invalid：上一个不满足 minK ≤ nums[i] ≤ maxK 的位置（初始化为 −1）。
- last_min：上一个等于 minK 的位置（初始化为 −1）。
- last_max：上一个等于 maxK 的位置（初始化为 −1）。
从左至右遍历数组，每到索引 i：
- 若 nums[i] < minK 或 nums[i] > maxK，则更新 last_invalid = i。
- 若 nums[i] == minK，则更新 last_min = i。
- 若 nums[i] == maxK，则更新 last_max = i。
以 i 结尾的所有合法子数组，起始点必须在 (last_invalid, min(last_min, last_max)] 之间，故可累加 max(0, min(last_min, last_max) - last_invalid) 到答案中。
最终累加得到所有定界子数组的数量。

时间复杂度

时间复杂度： $O(n)$ ，其中 $n$ 为数组长度
空间复杂度： $O(1)$ （仅使用常数额外变量）

代码实现

class Solution:
    def countSubarrays(self, nums: list[int], minK: int, maxK: int) -> int:
        last_invalid = -1     # 最后一个不在 [minK, maxK] 范围内的索引
        last_min = -1         # 最后一个出现 minK 的索引
        last_max = -1         # 最后一个出现 maxK 的索引
        count = 0             # 结果计数

        for i, x in enumerate(nums):
            # 1）如果 x 超出 [minK, maxK] 区间，则标记为无效
            if x < minK or x > maxK:
                last_invalid = i

            # 2）记录最新出现 minK 和 maxK 的位置
            if x == minK:
                last_min = i
            if x == maxK:
                last_max = i

            # 3）计算以 i 结尾的合法子数组个数
            #    起始点 j 必须 > last_invalid，且 ≤ min(last_min, last_max)
            valid_start = min(last_min, last_max)
            if valid_start > last_invalid:
                count += (valid_start - last_invalid)

        return count

以 nums = [1,3,5,2,7,5], minK = 1, maxK = 5为例：

i	nums[i]	last_invalid	last_min	last_max	min(last_min, last_max)	新增子数组 = max(0, min–last_invalid)	累计 count
-1	—	-1	-1	-1	—	—	0
0	1	-1	0	-1	-1	max(0, -1 − (-1)) = 0	0
1	3	-1	0	-1	-1	max(0, -1 − (-1)) = 0	0
2	5	-1	0	2	0	max(0, 0 − (-1)) = 1	1
3	2	-1	0	2	0	max(0, 0 − (-1)) = 1	2
4	7 (>5)	4	0	2	0	max(0, 0 − 4) = 0	2
5	5	4	0	5	0	max(0, 0 − 4) = 0	2

i=2 时，nums[2]=5，更新 last_max=2，此时 min(last_min,last_max)=0，新增子数组有 1 个，即 [1,3,5]。
i=3 时，nums[3]=2，没有更新 last_min/last_max，但依然可延伸前面那个“有效段”贡献 1 个，即 [1,3,5,2]。
i=4 时跳到 7（无效），last_invalid=4，后续以任何 i≥4 结尾的子数组都必须从 5 之后开始；此时在位置 5 上虽然又出现了 maxK，但最早的 minK 还是在 0，所以 min(last_min,last_max)=0≤ last_invalid=4，无有效子数组。

最终总数为 2。

边界

minK == maxK
算法依然适用，此时要求子数组内所有元素都等于同一个值 K，也就统计所有连续等于 K 的子数组个数。
数组中无 minK 或 maxK
某一关键位置永远为 −1，则 min(last_min,last_max) = −1，每次贡献都为 0，最终答案 0。
整型溢出
累加次数最多是 $\mathcal{O}(n^2/2)$ 级别（当所有子数组都合法时），对于 n≤ $10^5$ ，要用 64 位整型（Python 中 int 自动大整型）。