1438. 绝对差不超过限制的最长连续子数组

题目链接（中等）

题目描述

给你一个整数数组 nums 和一个整数 limit。

请你返回 最长非空子数组 的长度，要求该子数组中 任意两个元素 之间的差的 绝对值 都 小于或等于 limit。

数据范围：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

示例

示例 1：

输入： nums = [8,2,4,7], limit = 4
输出： 2
解释： 所有子数组中，只有长度为 1 或 2 的子数组满足条件。最长的是 [8,2]? 不，|8-2|=6>4，实际最长是 [2,4] 或 [4,7]，长度为 2。

示例 2：

输入： nums = [10,1,2,4,7,2], limit = 5
输出： 4
解释： 子数组 [2,4,7,2] 满足条件，最大绝对差 |7-2| = 5 ≤ 5。

示例 3：

输入： nums = [4,2,2,2,4,4,2,2], limit = 0
输出： 3
解释： 由于 limit = 0，子数组内所有元素必须相等，最长连续相同元素为 [2,2,2]，长度 3。

核心思路

关键观察：子数组中「任意两元素之差的绝对值 ≤ limit」等价于：

$$\max(\text{子数组}) - \min(\text{子数组}) \le \text{limit}$$

也就是说，只需要关注子数组的最大值和最小值。

于是问题转化为：找最长的滑动窗口，使得窗口内 max - min <= limit。

滑动窗口的思路：

1. 右指针 right 不断向右扩展，把 nums[right] 加入窗口；
2. 若窗口内 max - min > limit，左指针 left 向右收缩，直到条件满足；
3. 每次更新答案 ret = max(ret, right - left + 1)。

核心难点：如何高效维护窗口内的最大值和最小值？

两种方法：

1. 有序集合：把窗口元素放入有序集合，s[0] 是最小值，s[-1] 是最大值，$O(\log n)$ 插入/删除；
2. 单调队列：用两个双端队列分别维护窗口内的最小值和最大值，$O(1)$ 摊还操作，总时间 $O(n)$。

---

方法一：滑动窗口 + 有序集合

思路及解法

用 SortedList（有序集合）维护当前窗口内的所有元素：

• s[0] 是窗口最小值；
• s[-1] 是窗口最大值；
• 加入 / 删除元素 $O(\log n)$。

流程：

1. 初始化空的有序集合 s，left = right = ret = 0；
2. 右指针 right 从 0 到 n-1：
   • s.add(nums[right])；
   • 当 s[-1] - s[0] > limit 时，s.remove(nums[left])，left += 1；
   • ret = max(ret, right - left + 1)；
3. 返回 ret。

代码

from sortedcontainers import SortedList

class Solution:
    def longestSubarray(self, nums: list[int], limit: int) -> int:
        s = SortedList()
        n = len(nums)
        left = right = ret = 0

        while right < n:
            s.add(nums[right])
            while s[-1] - s[0] > limit:
                s.remove(nums[left])
                left += 1
            ret = max(ret, right - left + 1)
            right += 1

        return ret

sortedcontainers 不是 Python 标准库，LeetCode 平台支持，但本地运行需要 pip install sortedcontainers。

复杂度分析

• 时间复杂度：$O(n \log n)$，每次 add / remove 是 $O(\log n)$，每个元素最多各操作一次。
• 空间复杂度：$O(n)$，有序集合最多存 n 个元素。

---

方法二：滑动窗口 + 单调队列（推荐）

思路及解法

用两个单调队列分别维护窗口内的最小值和最大值：

• queMin：单调递增队列，队首是窗口最小值；
• queMax：单调递减队列，队首是窗口最大值。

维护规则：

• 加入 nums[right] 时：
  • queMin：弹出队尾所有 > nums[right] 的元素，再入队；
  • queMax：弹出队尾所有 < nums[right] 的元素，再入队；
• 检查条件 queMax[0] - queMin[0] > limit 时，left 右移，若 nums[left] 正好是队首元素，则队首出队。

为什么可以用单调队列：

• 对于最小值，如果新元素比队尾小，队尾元素永远不会再成为窗口最小值（因为有更小的新元素在它右边），可以直接弹出；
• 最大值同理。

流程：

1. 初始化两个 deque，left = right = ret = 0；
2. 右指针 right 从 0 到 n-1：
   • 维护 queMax：弹出队尾 < nums[right] 的，入队 nums[right]；
   • 维护 queMin：弹出队尾 > nums[right] 的，入队 nums[right]；
   • 当 queMax[0] - queMin[0] > limit 时：
     • 若 nums[left] == queMin[0]，queMin.popleft()；
     • 若 nums[left] == queMax[0]，queMax.popleft()；
     • left += 1；
   • ret = max(ret, right - left + 1)；
3. 返回 ret。

代码

from collections import deque

class Solution:
    def longestSubarray(self, nums: list[int], limit: int) -> int:
        n = len(nums)
        queMax, queMin = deque(), deque()
        left = right = ret = 0

        while right < n:
            # 维护单调递减队列（最大值）
            while queMax and queMax[-1] < nums[right]:
                queMax.pop()
            queMax.append(nums[right])

            # 维护单调递增队列（最小值）
            while queMin and queMin[-1] > nums[right]:
                queMin.pop()
            queMin.append(nums[right])

            # 窗口不合法，收缩左边界
            while queMax[0] - queMin[0] > limit:
                if nums[left] == queMin[0]:
                    queMin.popleft()
                if nums[left] == queMax[0]:
                    queMax.popleft()
                left += 1

            ret = max(ret, right - left + 1)
            right += 1

        return ret

复杂度分析

• 时间复杂度：$O(n)$，每个元素最多入队、出队一次。
• 空间复杂度：$O(n)$，两个队列最坏情况下各存 n 个元素。

---

两种方法对比

方法	时间	空间	特点
有序集合	$O(n \log n)$	$O(n)$	代码简洁，依赖第三方库
单调队列	$O(n)$	$O(n)$	最优解，面试首选

推荐：

• 面试：首选单调队列，时间复杂度 $O(n)$，且不依赖第三方库；
• 快速实现：有 sortedcontainers 时，有序集合代码更短。

---

关键细节

1. 为什么只需要看 max - min

「任意两元素之差的绝对值 ≤ limit」等价于「最大值与最小值之差 ≤ limit」。

证明：

• 必要性：最大值和最小值也是子数组中的两个元素，它们的差必须 ≤ limit；
• 充分性：任意两元素 a, b 都满足 min ≤ a, b ≤ max，所以 |a - b| ≤ max - min ≤ limit。

2. 为什么滑动窗口是单调的

当 right 向右扩展时，窗口变大，max - min 不会减小，只会增大或不变。所以当窗口不合法时，只需 left 右移即可，不需要回溯 right。

3. 单调队列的出队条件

• 入队时：queMax 弹出队尾 < nums[right] 的，保持递减；queMin 弹出队尾 > nums[right] 的，保持递增；
• 出队时：只有 nums[left] 恰好等于队首元素时，才需要 popleft，否则队首不是被移出的元素。

为什么不用判断其他位置：单调队列的队首一定是窗口的极值，若 nums[left] 不是极值，它早就在入队时被弹掉了（被更大的值或更小的值挤掉），所以不需要处理。

4. 单调队列中存值而不是下标

本题只需要比较值和判断队首是否等于 nums[left]，存值就够了。若需要判断元素是否还在窗口内（比如求固定长度窗口最大值），则需要存下标。

5. 与 LC 239 滑动窗口最大值的区别

• LC 239：固定窗口大小 k，求每个窗口的最大值；
• LC 1438：窗口大小可变，要求窗口内 max - min ≤ limit，求最长窗口。

LC 239 只需要一个单调队列，LC 1438 需要两个（一个维护最大值，一个维护最小值）。

6. 边界情况

• limit = 0：窗口内所有元素必须相等，等价于求最长连续相同元素；
• 所有元素相同：答案 n；
• n = 1：答案 1。

---

总结

• 核心转化：「任意两元素之差 ≤ limit」⟺「max - min ≤ limit」；
• 滑动窗口：右指针扩展，不合法时左指针收缩；
• 有序集合：SortedList 维护窗口，$O(n \log n)$；
• 单调队列：两个双端队列分别维护 max 和 min，$O(n)$；
• 易错点：
  • 出队时要判断 nums[left] 是否等于队首；
  • 单调队列的入队条件要保持单调性；
• 通用套路：「窗口内极值约束」→ 滑动窗口 + 单调队列。

相关题目

• LC 239. 滑动窗口最大值（固定窗口 + 单调队列）239. 滑动窗口最大值
• LC 76. 最小覆盖子串（滑动窗口 + 哈希表）
• LC 1004. 最大连续 1 的个数 III（滑动窗口 + 计数）
• LC 220. 存在重复元素 III（滑动窗口 + 有序集合）220. 存在重复元素 III
• LC 424. 替换后的最长重复字符（滑动窗口 + 计数）