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^51 nums[i] 10^90 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找到插入位置用有序数组的长度反推窗口左边界实现单指针滑动代码语言支持Python3class 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库的SortedListJava 可用TreeMapC 可用multiset有序集合自动维护内部有序性d[0]即窗口最小值、d[-1]即窗口最大值窗口合法性的判断与收缩逻辑和解法一保持一致。关键点平衡二叉树优化插入和删除的时间复杂度与解法一共享同一套滑动窗口 极值差框架仅替换数据结构代码语言支持Python3from 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]接下来处理2q1递减[8]2 比队尾 8 小直接入队 →[8,2]仍在维护中q2递增[8,2]2 比队尾 8 小弹出 8 后入队 →[2]注意此时无需管 q2 内部差大于 limit合法性判断统一在最大值 - 最小值处进行。接下来处理4q1递减[8,4]q2递增[4]4 比队尾 2 大弹出 2 后入队接下来处理7q1递减[8,7]q2递增[7]7 比队尾 4 大弹出 4 后入队当q1[0] - q2[0] limit时说明当前窗口不合法需要移动左指针i收缩窗口收缩时若左边界元素恰是某队列队首则将其popleft()出队。关键点单调队列获取最大最小值q1 单调递减取最大值q2 单调递增取最小值窗口收缩时同步从队列头部弹出过期的左边界元素代码语言支持Python3q1是单调递减的队列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. 滑动窗口中位数有序结构维护中位数共享的思想内核。延伸阅读滑动窗口思路 模板可变窗口与固定窗口的完整套路与伪代码单调栈单调结构的通用模板与哨兵法技巧239. 滑动窗口最大值单单调队列求窗口最大值480. 滑动窗口中位数有序结构 滑动窗口的进阶应用二分查找讲义bisect.insort等二分定位的前置知识【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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^51 nums[i] 10^90 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找到插入位置用有序数组的长度反推窗口左边界实现单指针滑动代码语言支持Python3class 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库的SortedListJava 可用TreeMapC 可用multiset有序集合自动维护内部有序性d[0]即窗口最小值、d[-1]即窗口最大值窗口合法性的判断与收缩逻辑和解法一保持一致。关键点平衡二叉树优化插入和删除的时间复杂度与解法一共享同一套滑动窗口 极值差框架仅替换数据结构代码语言支持Python3from 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]接下来处理2q1递减[8]2 比队尾 8 小直接入队 →[8,2]仍在维护中q2递增[8,2]2 比队尾 8 小弹出 8 后入队 →[2]注意此时无需管 q2 内部差大于 limit合法性判断统一在最大值 - 最小值处进行。接下来处理4q1递减[8,4]q2递增[4]4 比队尾 2 大弹出 2 后入队接下来处理7q1递减[8,7]q2递增[7]7 比队尾 4 大弹出 4 后入队当q1[0] - q2[0] limit时说明当前窗口不合法需要移动左指针i收缩窗口收缩时若左边界元素恰是某队列队首则将其popleft()出队。关键点单调队列获取最大最小值q1 单调递减取最大值q2 单调递增取最小值窗口收缩时同步从队列头部弹出过期的左边界元素代码语言支持Python3q1是单调递减的队列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. 滑动窗口中位数有序结构维护中位数共享的思想内核。延伸阅读滑动窗口思路 模板可变窗口与固定窗口的完整套路与伪代码单调栈单调结构的通用模板与哨兵法技巧239. 滑动窗口最大值单单调队列求窗口最大值480. 滑动窗口中位数有序结构 滑动窗口的进阶应用二分查找讲义bisect.insort等二分定位的前置知识【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考