What is a continuous subarray in this problem?

A continuous subarray is any contiguous sequence of nums where the difference between maximum and minimum values satisfies the window constraint.

How does the sliding window approach apply to Continuous Subarrays?

Sliding window dynamically expands and contracts while maintaining max-min state to count valid subarrays efficiently.

Can this approach handle large arrays up to 10^5 elements?

Yes, using O(n) time with monotonic queues ensures performance even for the maximum constraints.

Why use monotonic queues instead of sorting each window?

Sorting each window would be O(n^2) or worse. Monotonic queues maintain max-min in O(1) per element, keeping overall time O(n).

How do I count all valid subarrays without missing any?

For each right pointer, count subarrays from left to right by adding (right-left+1) whenever the window is valid, updating left when constraints break.

#2762

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

不间断子数组

给你一个下标从 0 开始的整数数组 nums 。 nums 的一个子数组如果满足以下条件，那么它是不间断的： i ， i + 1 ，...， j 表示子数组中的下标。对于所有满足 i 1 , i 2 的下标对，都有 0 1 ] - nums[i 2 ]| 。请你返回不间断子数组的总数目。 …

数组队列滑动窗口堆（优先队列）有序集合

题目描述

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

i，i + 1 ，...，j 表示子数组中的下标。对于所有满足 i <= i₁, i₂ <= j 的下标对，都有 0 <= |nums[i₁] - nums[i₂]| <= 2 。

请你返回 不间断 子数组的总数目。

子数组是一个数组中一段连续非空的元素序列。

示例 1：

输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。

示例 2：

输入：nums = [1,2,3]
输出：6
解释：
大小为 1 的不间断子数组：[1], [2], [3] 。
大小为 2 的不间断子数组：[1,2], [2,3] 。
大小为 3 的不间断子数组：[1,2,3] 。
不间断子数组的总数目为 3 + 2 + 1 = 6 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：有序列表 + 双指针

我们可以用双指针 $i$ 和 $j$ 维护当前子数组的左右端点，用一个有序列表维护当前子数组的所有元素。

遍历数组 $nums$ ，对于当前遍历到的数字 $nums[i]$ ，我们将其加到有序列表中，如果此时有序列表中的最大值与最小值的差值大于 $2$ ，那么我们循环右移指针 $i$ ，不断将 $nums[i]$ 从有序列表中移出，直到列表为空或者有序列表元素的最大差值不大于 $2$ 。此时不间断的子数组数目为 $j - i + 1$ ，我们将其添加到答案中。

遍历结束，返回答案即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        ans = i = 0
        sl = SortedList()
        for x in nums:
            sl.add(x)
            while sl[-1] - sl[0] > 2:
                sl.remove(nums[i])
                i += 1
            ans += len(sl)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Looks for a sliding window with dynamic state updates.
question_mark
Checks understanding of monotonic queue usage for max-min tracking.
question_mark
May ask how to handle large arrays efficiently in O(n).

warning

常见陷阱

外企场景

error
Forgetting to shrink the window when max-min exceeds allowed range.
error
Incorrectly updating monotonic queues when elements leave the window.
error
Counting subarrays incorrectly by not considering all subarrays ending at current index.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute subarrays with sum constraints instead of max-min differences.
arrow_right_alt
Count subarrays with exactly k distinct elements using similar sliding window techniques.
arrow_right_alt
Find the longest continuous subarray under the same max-min constraint.

help

常见问题

外企场景

继续练习

#1438 绝对差不超过限制的最长连续子数组 #2398 预算内的最多机器人数目 #2944 购买水果需要的最少金币数