文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载本文基于 algorithm-base 仓库的《leetcode1438绝对值不超过限制的最长子数组》讲解文档系统拆解 LeetCode 1438 的解题思路用可变长度滑动窗口框定候选区间用单调递减双端队列与单调递增双端队列分别维护窗口内的最大值与最小值从而在 O(n) 时间内求解。读完本文你将掌握滑动窗口 双端队列这一组合拳的完整推导过程、多语言实现细节与常见易错点并能迁移到仓库中的滑动窗口最大值、队列最大值、最小栈等相关题目。一、题目回顾给你一个整数数组nums和一个表示限制的整数limit请你返回最长连续子数组的长度该子数组中的任意两个元素之间的绝对差必须小于或者等于limit。如果不存在满足条件的子数组则返回 0。示例输入nums [10,1,2,4,7,2],limit 5输出4解释满足题意的最长子数组是[2,4,7,2]其最大绝对差|2-7| 5 5。提示数据范围参数取值范围说明nums.length1 nums.length 10^5数组规模较大要求算法复杂度接近线性nums[i]1 nums[i] 10^9元素可正可负、值域很大无法用值域数组统计limit0 limit 10^9限制可以为零即窗口内所有元素必须相等这道题是经典的可变长度滑动窗口题目解法与仓库中剑指 Offer 59 - I. 滑动窗口的最大值一脉相承核心都是单调双端队列。二、破题思路把问题拆成求窗口内最大/最小值先思考一个关键问题如何判断某个连续子数组是否满足条件条件说任意两个元素之间的绝对差 ≤ limit而一组数中任意两数的绝对差的最大值必然出现在最大值与最小值之间。因此窗口内最大绝对差 窗口最大值 - 窗口最小值只要窗口最大值 - 窗口最小值 limit该窗口就合法否则不合法。于是原问题被等价地转化为两个子问题获取滑动窗口内的最大值获取滑动窗口内的最小值。滑动窗口的最大值正是仓库中滑动窗口的最大值这篇文档解决的问题——当时我们借助双端队列维护了一个单调递减队列队头即窗口最大值。本题完全复用该思想再额外维护一个单调递增队列来获取窗口最小值即可。也就是说我们可以同时维护两条单调队列maxdeque单调递减的双端队列队头是当前窗口的最大值mindeque单调递增的双端队列队头是当前窗口的最小值。窗口是否符合要求只需看maxdeque 队头 - mindeque 队头是否 ≤limit满足则右指针继续扩大窗口求最长不满足则左指针收缩窗口直到重新满足为止。循环结束后返回出现过的最长窗口长度。三、前置知识双端队列与单调队列普通队列遵循先进先出只能一端入队、另一端出队双端队列Deque则允许在队头和队尾两端进行插入与删除不需要遵循先进先出规则。Java 中LinkedList实现了Deque接口Python 中collections.deque、Go 中用切片模拟、Swift 中可自实现均能胜任。单调队列指队列内部元素保持单调递增或递减的队列。以单调递减队列为例维护规则是新元素入队前从队尾弹出所有小于新元素的元素再让新元素入队这样队头永远是队列中最大的元素滑动窗口的最大值。原理解释那些被弹出的小元素在窗口内已经被更新的大元素覆盖它们在未来任何时刻都不可能再成为窗口最大值因为大元素存活时间更久且更大因此可以安全丢弃这就是单调队列高效的核心。对单调队列数据结构本身有疑问的读者可以先阅读仓库中的关于栈和队列的那些事与滑动窗口的最大值两篇前置文档。四、动画流程分步拆解以示例数据为例原始文档配有一段算法执行动画这里我们将其拆解为可核对的文字过程数据使用示例nums [10,1,2,4,7,2],limit 5。初始状态maxdeque []mindeque []left 0right 0maxwin 0。步骤rightnums[right]入队后maxdeque递减入队后mindeque递增队头差值是否收缩窗口区间maxwin1010[10][10]0 ≤ 5否[0,0]1211[10,1][1]10 被弹出9 5是left0时nums[0]10命中maxdeque队头弹出[1,1]1322[2]1 被弹出[1,2]1 ≤ 5否[1,2]2434[4]2 被弹出[1,2,4]3 ≤ 5否[1,3]3547[7]4 被弹出[1,2,4,7]6 5是left1时nums[1]1命中mindeque队头弹出[2,4]3652[7,2][2,2]7、4 被弹出5 ≤ 5否[2,5]4最终返回maxwin 4即最长合法子数组[2,4,7,2]。流程中两个核心动作值得反复体会扩大窗口入队right指向的新元素先清理两条队列的队尾分别维护递减/递增性质然后入队此时两条队列的队头即窗口的最大值和最小值收缩窗口出队当maxdeque队头与mindeque队头之差大于limit时left右移。只有恰好等于被移出元素nums[left]的队头才需要弹出——因为窗口左边界移出的是nums[left]本身若队头不是它说明该队头元素仍然留在窗口内不能被删除。五、复杂度分析时间复杂度 O(n)right与left均只向右移动、不回溯每个元素至多进入每条队列一次、至多被弹出一次因此均摊到每次操作是 O(1)整体为 O(n)。这正是面对10^5数据规模时的可行方案若用暴力枚举窗口再遍历求最大最小值复杂度为 O(n²) 或 O(n·k)会超时。空间复杂度 O(n)最坏情况下如数组严格单调递增且limit极大maxdeque或mindeque会保存窗口内所有元素因此为 O(n)实际通常等于窗口大小。六、多语言完整实现Java 实现import java.util.*; class Solution { public int longestSubarray(int[] nums, int limit) { // 单调递减双端队列队头为当前窗口最大值 DequeInteger maxdeque new LinkedList(); // 单调递增双端队列队头为当前窗口最小值 DequeInteger mindeque new LinkedList(); int len nums.length; int right 0, left 0, maxwin 0; while (right len) { // 维护 maxdeque弹出队尾所有小于新元素的元素保持单调递减 while (!maxdeque.isEmpty() maxdeque.peekLast() nums[right]) { maxdeque.removeLast(); } // 维护 mindeque弹出队尾所有大于新元素的元素保持单调递增 while (!mindeque.isEmpty() mindeque.peekLast() nums[right]) { mindeque.removeLast(); } // 新元素分别入队 maxdeque.addLast(nums[right]); mindeque.addLast(nums[right]); // 窗口不合法最大绝对差超过 limit时收缩左边界 while (maxdeque.peekFirst() - mindeque.peekFirst() limit) { // 若被移出窗口的元素恰好是队头元素则弹出队头 if (maxdeque.peekFirst() nums[left]) maxdeque.removeFirst(); if (mindeque.peekFirst() nums[left]) mindeque.removeFirst(); left; } // 保留最大窗口长度 maxwin Math.max(maxwin, right - left 1); right; } return maxwin; } }注意maxdeque.peekFirst() nums[left]这里比较的是Integer与int会发生自动拆箱比较的是数值而若两个操作数都是Integer包装类型则应改用equals()比较值细节详见下文实现细节小节。Python 实现from typing import List import collections class Solution: def longestSubarray(self, nums: List[int], limit: int) - int: maxdeque collections.deque() # 单调递减队头为窗口最大值 mindeque collections.deque() # 单调递增队头为窗口最小值 leng len(nums) right 0 left 0 maxwin 0 while right leng: # 维护 maxdeque 单调递减 while len(maxdeque) ! 0 and maxdeque[-1] nums[right]: maxdeque.pop() # 维护 mindeque 单调递增 while len(mindeque) ! 0 and mindeque[-1] nums[right]: mindeque.pop() maxdeque.append(nums[right]) mindeque.append(nums[right]) # 收缩窗口 while (maxdeque[0] - mindeque[0]) limit: if maxdeque[0] nums[left]: maxdeque.popleft() if mindeque[0] nums[left]: mindeque.popleft() left 1 # 保留最大窗口 maxwin max(maxwin, right - left 1) right 1 return maxwinPython 的collections.deque是真正的双向链表实现pop()队尾出队与popleft()队头出队均为 O(1)。Go 实现func longestSubarray(nums []int, limit int) int { maxdeq : []int{} // 递减队列队头为窗口最大值 mindeq : []int{} // 递增队列队头为窗口最小值 length : len(nums) left, right, maxwin : 0, 0, 0 for right length { // 维护 maxdeq 单调递减 for len(maxdeq) ! 0 maxdeq[len(maxdeq)-1] nums[right] { maxdeq maxdeq[:len(maxdeq)-1] } maxdeq append(maxdeq, nums[right]) // 维护 mindeq 单调递增 for len(mindeq) ! 0 mindeq[len(mindeq)-1] nums[right] { mindeq mindeq[:len(mindeq)-1] } mindeq append(mindeq, nums[right]) // 收缩窗口 for maxdeq[0]-mindeq[0] limit { if maxdeq[0] nums[left] { maxdeq maxdeq[1:] } if mindeq[0] nums[left] { mindeq mindeq[1:] } left } maxwin max(maxwin, right-left1) right } return maxwin } func max(a, b int) int { if a b { return a } return b }Go 版本直接用切片模拟双端队列maxdeq[:len(maxdeq)-1]弹出队尾、maxdeq[1:]弹出队头、append从队尾入队。注意 Go 官方从 1.21 起标准库已内置max内置函数示例中自定义max是为了兼容旧版本 Go两者选一即可。Swift 实现两种写法写法一数组模拟会超时原文档实测 58 / 61 个用例通过class Solution { func longestSubarray(_ nums: [Int], _ limit: Int) - Int { var maxQueue: [Int] [] var minQueue: [Int] [] let len nums.count var right 0, left 0, maxWin 0 while right len { while !maxQueue.isEmpty (maxQueue.last! nums[right]) { maxQueue.removeLast() } while !minQueue.isEmpty (minQueue.last! nums[right]) { minQueue.removeLast() } maxQueue.append(nums[right]) minQueue.append(nums[right]) while (maxQueue.first! - minQueue.first!) limit { if maxQueue.first! nums[left] { maxQueue.removeFirst() } if minQueue.first! nums[left] { minQueue.removeFirst() } left 1 } maxWin max(maxWin, right - left 1) right 1 } return maxWin } }超时原因Swift 数组的removeFirst()需要把后续所有元素前移是 O(n) 操作在最坏情况下整体退化为 O(n²)。这是典型的数组实现双端队列陷阱。写法二自实现环形缓冲双端队列Deque两端操作均为 O(1)原文档实测可通过全部用例class Solution { func longestSubarray(_ nums: [Int], _ limit: Int) - Int { var maxQueue DequeInt.init() var minQueue DequeInt.init() let len nums.count var right 0, left 0, maxWin 0 while right len { while !maxQueue.isEmpty (maxQueue.peekBack()! nums[right]) { maxQueue.dequeueBack() } while !minQueue.isEmpty (minQueue.peekBack()! nums[right]) { minQueue.dequeueBack() } maxQueue.enqueue(nums[right]) minQueue.enqueue(nums[right]) while (maxQueue.peekFront()! - minQueue.peekFront()!) limit { if maxQueue.peekFront()! nums[left] { maxQueue.dequeue() } if minQueue.peekFront()! nums[left] { minQueue.dequeue() } left 1 } maxWin max(maxWin, right - left 1) right 1 } return maxWin } // 双端队列数据结构底层用 [T?] 数组 head 游标采用惰性清理 容量收缩策略 public struct DequeT { private var array: [T?] private var head: Int private var capacity: Int private let originalCapacity: Int public init(_ capacity: Int 10) { self.capacity max(capacity, 1) originalCapacity self.capacity array T? head capacity } public var isEmpty: Bool { return count 0 } public var count: Int { return array.count - head } public mutating func enqueue(_ element: T) { array.append(element) } public mutating func enqueueFront(_ element: T) { if head 0 { capacity * 2 let emptySpace T? array.insert(contentsOf: emptySpace, at: 0) head capacity } head - 1 array[head] element } public mutating func dequeue() - T? { guard head array.count, let element array[head] else { return nil } array[head] nil head 1 if capacity originalCapacity head capacity * 2 { let amountToRemove capacity capacity / 2 array.removeFirst(amountToRemove) head - amountToRemove capacity / 2 } return element } public mutating func dequeueBack() - T? { if isEmpty { return nil } else { return array.removeLast() } } public func peekFront() - T? { if isEmpty { return nil } else { return array[head] } } public func peekBack() - T? { if isEmpty { return nil } else { return array.last! } } } }这段Deque结构体的设计要点底层用[T?]定长数组head游标标记逻辑队头出队时只把位置置nil并移动head不移动数组元素从而让队头出队达到 O(1)当队头空间被消耗过多head capacity * 2时一次性清理数组前部的空洞并收缩容量保证空间不会无限膨胀均摊复杂度仍为 O(1)。七、实现细节与易错点两条队列的单调方向不可搞反maxdeque是单调递减队头最大mindeque是单调递增队头最小。入队时比较条件分别是与写反会导致队头语义错误。窗口收缩时队头弹出的条件只有当nums[left]恰好等于队头元素时才弹出对应队头。因为left移动意味着该元素离开窗口若队头元素不等于它说明队头元素仍在窗口内必须保留。left与right的单调性right只增不减不断扩大右边界left只增不减不断收缩左边界保证每个可能的窗口恰好被检查一次不会遗漏也不会重复。limit 0的退化情况此时要求窗口内所有元素相等算法依然成立——不相等时最大差值必然大于 0触发收缩。Java 包装类型比较若比较双方都是Integer如从DequeInteger中取出两个元素直接比较应当用equals()而非-128 ~ 127之外的整数值比较的是引用。本题代码中Deque元素与nums[left]int比较会自动拆箱是安全的但仓库剑指 Offer 59 - II. 队列的最大值中的pop_front明确指出que.peek().equals(deq.peekFirst())必须使用equals()这是同一类坑。Swift 数组removeFirst()是 O(n)不要用原生数组的队头删除模拟双端队列做高频操作否则会超时应使用自实现的环形双端队列或真正的双向队列结构。八、算法正确性论证整个算法依赖以下三条不变式从代码结构可以验证不变式 1最大值正确性maxdeque始终单调递减队头恒为当前窗口[left, right]内的最大值。因为入队前已弹出队尾所有更小元素而队头元素若小于新元素则必然已被弹出。不变式 2最小值正确性mindeque始终单调递增队头恒为当前窗口内的最小值论证对称。不变式 3窗口合法性判定充分必要对任意窗口maxdeque.peekFirst() - mindeque.peekFirst()即窗口内最大绝对差。合法 ⇔ 该差值 ≤limit。收缩只在违反条件时进行且每次只移动一格left保证不会跳过任何合法窗口。由于right遍历完全部元素、left始终维护以right为右端点的最长合法窗口因此算法结束时maxwin必然是所有合法窗口长度的最大值。九、举一反三仓库内相关题目串联理解了单调双端队列维护窗口极值之后可以在 algorithm-base 仓库中顺着这条线继续刷题形成知识网络题目仓库文档与本题的关系剑指 Offer 59 - I. 滑动窗口的最大值滑动窗口的最大值固定窗口大小 单条单调递减队列是本题的直接前置知识剑指 Offer 59 - II. 队列的最大值队列的最大值单调双端队列辅助普通队列动态取极值的模板题155. 最小栈最小栈用辅助栈在 O(1) 内取最小值思路与辅助队列同源739. 每日温度每日温度单调栈的经典应用可与单调队列对比学习42. 接雨水接雨水单调栈求解的进阶题目209. 长度最小的子数组长度最小的子数组不带极值维护的纯滑动窗口先掌握基础窗口收缩模型十、小结LeetCode 1438 的核心价值在于两点一是把任意两元素绝对差这一看似复杂的条件化简为窗口最大值 - 窗口最小值这一可实时维护的度量二是展示了可变滑动窗口 双端单调队列的组合模板——一条队列维护最大值、一条队列维护最小值任何需要动态维护窗口极值的场景都可以套用。掌握了本题再遇到窗口内最大值与最小值之差滑动窗口的最大值队列的最大值等问题时就能举一反三、快速套用。本文所依据的原始讲解文档位于 animation-simulation/数组篇/leetcode1438绝对值不超过限制的最长子数组.md同目录下还收录了 长度最小的子数组 等数组篇滑动窗口题目可配合阅读README 中提供了整个仓库的题目索引与进阶路线。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐LeetCode 1438 题解绝对差不超过限制的最长连续子数组滑动窗口 双单调队列LeetCode 1438 题解绝对差不超过限制的最长连续子数组滑动窗口 双单调队列 导读 本题LeetCode 1438Longest Cont示例工程LeetCode 1438 最长连续子数组绝对差不超过限制滑动窗口 单调双端队列全解法解析LeetCode 1438 最长连续子数组绝对差不超过限制滑动窗口 单调双端队列全解法解析 本篇技术指南以 LeetCode 1438「Longest示例工程教程LeetCode 1438 题解绝对差不超过限制的最长连续子数组滑动窗口 有序集合 / 双单调队列LeetCode 1438 题解绝对差不超过限制的最长连续子数组滑动窗口 有序集合 / 双单调队列 本篇以仓库文档 problems/1438.lon文档教程知识库上一篇Oppia 开源项目教程下一篇推荐SlideMenuControllerSwift —— 优雅的侧滑菜单控制器创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考