LeetCode 1438 题解：绝对差不超过限制的最长连续子数组（滑动窗口 + 有序集合 / 双单调队列）-迪斯科星球

LeetCode 1438 题解：绝对差不超过限制的最长连续子数组（滑动窗口 + 有序集合 / 双单调队列）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇以仓库文档 problems/1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md 为核心，完整讲解"求满足最大值与最小值之差不大于 limit 的最长连续子数组"的三种解法：二分 + 有序数组、平衡树（SortedList）以及双单调队列，并给出可复制的 Python3 实现与复杂度分析。读完你将掌握"滑动窗口 + 有序数据结构"这一处理连续区间极值类题目的通用套路，并能将其迁移到 239 滑动窗口最大值、480 滑动窗口中位数等同源题目上。

题目描述

给你一个整数数组nums和一个表示限制的整数limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于limit。

如果不存在满足条件的子数组，则返回 0。

示例 1：

输入：nums = [8,2,4,7], limit = 4 输出：2 解释：所有子数组如下： [8] 最大绝对差 |8-8| = 0 <= 4. [8,2] 最大绝对差 |8-2| = 6 > 4. [8,2,4] 最大绝对差 |8-2| = 6 > 4. [8,2,4,7] 最大绝对差 |8-2| = 6 > 4. [2] 最大绝对差 |2-2| = 0 <= 4. [2,4] 最大绝对差 |2-4| = 2 <= 4. [2,4,7] 最大绝对差 |2-7| = 5 > 4. [4] 最大绝对差 |4-4| = 0 <= 4. [4,7] 最大绝对差 |4-7| = 3 <= 4. [7] 最大绝对差 |7-7| = 0 <= 4. 因此，满足题意的最长子数组的长度为 2 。

示例 2：

输入：nums = [10,1,2,4,7,2], limit = 5 输出：4 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：

输入：nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3

提示：

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

前置知识

有序集合
二分法（可参考仓库专题二分查找讲义）
滑动窗口（思路 + 模板）
单调栈

题目分析：核心是"窗口内最大最小值的差"

判断一个连续子数组是否满足条件，关键在于该子数组的最大值与最小值的差是否不超过 limit。因为子数组内任意两个元素的绝对差，最大值恰好就是"最大值 - 最小值"。因此问题转化为：

在滑动窗口内，实时维护（或快速查询）最大值与最小值，一旦max - min > limit，就收缩窗口左边界。

由于数据是静态的、无需区间修改，因此并不需要线段树等高级数据结构。本仓库给出了三种由慢到快、思路层层递进的解法，下面逐一展开。

解法一：二分法 + 有序数组（O(n²)）

思路

这里手动维护一个有序数组d，其中的数据表示某一个连续子数组，只不过d是已经排好序的。比如原有的子数组是[3,1,2]，那么d就是[1,2,3]。

我们可以使用二分法在O(log n)的时间内找到插入点，并在最坏O(n)的时间内完成插入和删除。因此最坏时间复杂度是O(n²)。

接下来使用滑动窗口技巧，代码上可使用双指针。由于d的长度就是窗口的大小，因此只需一个指针表示右端点即可，因为左端点可通过右端点 - d 的长度 + 1得出：

left = i - len(d) + 1

当窗口内最大值与最小值之差d[-1] - d[0] > limit时，说明窗口不合法，需要把左端元素A[left]从d中删除（同时等价于窗口左边界右移）。

关键点

维护一个有序数组，并通过二分法（bisect.insort）找到插入位置
用有序数组的长度反推窗口左边界，实现单指针滑动

代码

语言支持：Python3

class Solution: def longestSubarray(self, A: List[int], limit: int) -> int: d = [] ans = 1 for i, a in enumerate(A): bisect.insort(d, a) if len(d) > 1: while d[-1] - d[0] > limit: d.remove(A[i - len(d)+1]) ans = max(ans, len(d)) return ans

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n^2)$。虽然插入位置用二分找到，但有序数组的插入和删除都要移动元素，最坏为 $O(n)$，整体即 $O(n^2)$
空间复杂度：$O(n)$

这种"有序数组 + 二分插入"的模式在仓库另一道题 480. 滑动窗口中位数中也有体现：该题同样维护一个大小为 k 的有序数组，用二分在 $O(logk)$ 时间定位、$O(k)$ 时间完成删除、$O(1)$ 时间完成插入。可见这是一种针对"静态区间有序化"的通用（但偏慢）手法。

解法二：有序集合（平衡树，O(n log n)）

思路

思路与解法一完全类似，区别仅在于将底层数据结构从数组换成平衡树，这样插入和删除的复杂度可降低到 $O(log n)$：

Python 使用sortedcontainers库的SortedList
Java 可用TreeMap
C++ 可用multiset

有序集合自动维护内部有序性，d[0]即窗口最小值、d[-1]即窗口最大值，窗口合法性的判断与收缩逻辑和解法一保持一致。

关键点

平衡二叉树优化插入和删除的时间复杂度
与解法一共享同一套"滑动窗口 + 极值差"框架，仅替换数据结构

代码

语言支持：Python3

from sortedcontainers import SortedList class Solution: def longestSubarray(self, A: List[int], limit: int) -> int: d = SortedList() ans = 1 for i, a in enumerate(A): d.add(a) if len(d) > 1: while d[-1] - d[0] > limit: d.remove(A[i - len(d)+1]) ans = max(ans, len(d)) return ans

复杂度分析

令 n 为数组长度。

时间复杂度：$O(nlogn)$，每个元素至多插入、删除一次，单次平衡树操作 $O(logn)$
空间复杂度：$O(n)$

解法三：双单调队列（O(n)）

思路

单调队列可以快速得到最大值和最小值，因此我们可以使用两个单调队列，分别维护窗口内区间的最大值和最小值，接下来的思路和上面类似——维护一个滑动窗口即可。

为什么需要两个队列而不是一个？因为一个单调队列只能单调增或单调减，只能回答"极值"中的一个；而本题目需要同时知道最大值和最小值，因此要用两个队列：一个单调递减（队首为最大值）、一个单调递增（队首为最小值），两个队列会存储窗口内所有的数（有重叠）。

关于单调队列/栈的通用模板，可参考仓库专题单调栈：其核心结论是"如果压栈之后仍然可以保持单调性，那么直接压；否则先弹出栈顶元素，直到压入之后可以保持单调性"。

为什么用队列而不是单调栈？因为我们需要移除左侧（窗口左边界）的元素，需要在两端进行操作，这正是队列的基本操作，而栈只能在一端操作。这一点与 239. 滑动窗口最大值中"必须使用双端队列来同时清理队首失效元素与队尾过小元素"的原因完全一致。

下面以nums = [8,2,4,7], limit = 4手工推演一遍，帮助理解两个队列的状态变化：

刚开始处理8：

单调递减队列 q1（队首为最大值）：[8]
单调递增队列 q2（队首为最小值）：[8]

接下来处理2：

q1（递减）：[8]（2 比队尾 8 小，直接入队 →[8,2]仍在维护中）
q2（递增）：[8,2]（2 比队尾 8 小，弹出 8 后入队 →[2]）

注意此时无需管 q2 内部差大于 limit，合法性判断统一在"最大值 - 最小值"处进行。

接下来处理4：

q1（递减）：[8,4]
q2（递增）：[4]（4 比队尾 2 大，弹出 2 后入队）

接下来处理7：

q1（递减）：[8,7]
q2（递增）：[7]（7 比队尾 4 大，弹出 4 后入队）

当q1[0] - q2[0] > limit时，说明当前窗口不合法，需要移动左指针i收缩窗口；收缩时若左边界元素恰是某队列队首，则将其popleft()出队。

关键点

单调队列获取最大最小值：q1 单调递减取最大值，q2 单调递增取最小值
窗口收缩时同步从队列头部弹出"过期的左边界元素"

代码

语言支持：Python3

q1是单调递减的队列，q2是单调递增的队列。因此q1[0]是最大值，q2[0]是最小值。

class Solution: def longestSubarray(self, A: List[int], limit: int) -> int: q1, q2 = collections.deque(), collections.deque() ans = 1 i = 0 for j, a in enumerate(A): while q1 and q1[-1] < a: q1.pop() q1.append(a) while q2 and q2[-1] > a: q2.pop() q2.append(a) while i < j and q1 and q2 and q1[0] - q2[0] > limit: if A[i] == q1[0]: q1.popleft() elif A[i] == q2[0]: q2.popleft() i += 1 ans = max(ans, j - i + 1) return ans

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$，每个元素最多入队出队各一次，均摊线性
空间复杂度：$O(n)$

三种解法对比与套路总结

解法	核心数据结构	单次插入/删除	总时间复杂度	空间复杂度
二分 + 有序数组	Python list +`bisect.insort`	定位 $O(logn)$，移动 $O(n)$	$O(n^2)$	$O(n)$
有序集合	`SortedList`/`TreeMap`/`multiset`	$O(logn)$	$O(nlogn)$	$O(n)$
双单调队列	两个`collections.deque`	$O(1)$ 均摊	$O(n)$	$O(n)$

三种解法的框架高度一致，都是：

快指针j向右扩展窗口，把新元素按序插入数据结构；
若窗口不合法（max - min > limit），移动慢指针i收缩，并从数据结构中删除被移出的元素；
每步用max(ans, 窗口长度)更新答案。

这正对应仓库滑动窗口（思路 + 模板）中"窗口大小不固定、求解最大的满足条件的窗口"这一类可变窗口的伪代码模板：

初始化慢指针 = 0 初始化 ans for 快指针 in 可迭代集合 更新窗口内信息 while 窗口内不符合题意 扩展或者收缩窗口 慢指针移动 更新答案 返回 ans

区别仅在于"窗口内信息"用什么结构维护：数组 + 二分、平衡树，还是双单调队列——这也是本仓库 239. 滑动窗口最大值（单队列维护最大值）与 480. 滑动窗口中位数（有序结构维护中位数）共享的思想内核。

企业官网建设流程全解析