LeetCode 题解工作台
统计定界子数组的数目
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。 nums 的定界子数组是满足下述条件的一个子数组： 子数组中的 最小值 等于 minK 。 子数组中的 最大值 等于 maxK 。 返回定界子数组的数目。 子数组是数组中的一个连续部分。 示例 1： 输入： nums = [1,3…
4
题型
7
代码语言
3
相关题
当前训练重点
困难 · 滑动窗口（状态滚动更新）
答案摘要
由题意，我们可以知道，定界子数组的所有元素都在区间 $[\textit{minK}, \textit{maxK}]$ 中，且最小值一定为 ，最大值一定为 。 我们遍历数组 ，统计以 为右端点的定界子数组的个数，然后将所有的个数相加即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个整数数组 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 <= 1051 <= nums[i], minK, maxK <= 106
解题思路
方法一：枚举右端点
由题意，我们可以知道，定界子数组的所有元素都在区间 中，且最小值一定为 ，最大值一定为 。
我们遍历数组 ，统计以 为右端点的定界子数组的个数，然后将所有的个数相加即可。
具体实现逻辑如下：
- 维护最近一个不在区间 中的元素的下标 ，初始值为 。那么当前元素 的左端点一定大于 。
- 维护最近一个值为 的下标 ，最近一个值为 的下标 ，初始值均为 。那么当前元素 的左端点一定小于等于 。
- 综上可知，以当前元素为右端点的定界子数组的个数为 。累加所有的个数即可。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
j1 = j2 = k = -1
ans = 0
for i, v in enumerate(nums):
if v < minK or v > maxK:
k = i
if v == minK:
j1 = i
if v == maxK:
j2 = i
ans += max(0, min(j1, j2) - k)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) as each element is visited once with constant-time updates for last seen indices. Space complexity is O(1) since only a few indices are stored, independent of array size. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can you do this in one pass using a sliding window?
- question_mark
Consider how to track last positions of minK, maxK, and invalid elements efficiently.
- question_mark
Check edge cases where minK equals maxK or repeated numbers appear.
常见陷阱
外企场景- error
Forgetting to reset when encountering an out-of-bound element.
- error
Incorrectly counting subarrays when minK or maxK repeats.
- error
Assuming all subarrays with minK and maxK are valid without checking intermediate elements.
进阶变体
外企场景- arrow_right_alt
Count subarrays where elements are within a dynamic range instead of fixed bounds.
- arrow_right_alt
Compute sum of lengths of fixed-bound subarrays instead of count.
- arrow_right_alt
Handle multiple pairs of minK and maxK for a single pass solution.