★ FEATURED ARTICLE 很多人第一次见到LeetCode 239“滑动窗口最大值”第一反应是这不就是暴力扫一遍的事嘛结果写完一提交超时提示挂脸上才意识到这道题没那么简单。作为热门100题里的常客它考察的其实并不是“你会不会求最大值”而是“你会不会维护一个动态集合的极值”——这背后是数据结构设计思想不是单纯的编码技巧。这篇文章我会把这道题的解题思路完整拆开从暴力解到双端队列单调方案从原理推导到代码实现再到面试中怎么把这道题讲出层次感一次说透。这道题我前前后后刷过三遍每次重做都有新收获。第一次只会暴力第二次学会了单调队列但写不对边界第三次才真正理解为什么存索引而不仅仅是存值。如果你也正卡在这道题上或者准备面试想把这题吃透这篇内容应该能帮你省下不少弯路。1. 先把题目“吃透”滑动窗口最大值的题眼在哪1.1 题目描述背后的真实诉求先看题面给定一个整数数组nums有一个大小为k的滑动窗口从数组最左侧移动到最右侧你只能看到窗口中的k个数字。窗口每次向右移动一位返回滑动窗口中的最大值组成的数组。举个例子nums [1, 3, -1, -3, 5, 3, 6, 7]窗口大小k 3移动过程就是窗口位置[1, 3, -1]最大值是3窗口右移一位变成[3, -1, -3]最大值是3再右移变成[-1, -3, 5]最大值是5依次类推最终结果是[3, 3, 5, 5, 6, 7]题目本身并不难理解难点在于数据规模。题目的约束条件里nums.length最大可以到 10 的 5 次方k的取值也很大。如果窗口每次移动都重新扫描一遍窗口里的k个元素总复杂度就是 O(n×k)当k接近 50000 时计算量是亿级别的超时几乎是必然的。所以这道题的“题眼”在于随着窗口滑动相邻两个窗口之间有 k-1 个元素是重叠的这些重叠元素的比较结果是完全可以复用的。暴力解法的问题不是它错了而是它每次都把已经比过的元素又重新比了一遍做了大量的无效劳动。理解了这一点优化方向就清楚了——怎么把重复的比较次数省掉让总体代价降下来。1.2 暴力解法为什么不行瓶颈到底在哪先写出最自然的暴力思路也方便对比后面的优化方案def maxSlidingWindow(nums, k): n len(nums) res [] for i in range(n - k 1): res.append(max(nums[i : i k])) return res这段代码思路完全正确max()内部就是一次 O(k) 的扫描。外层循环 n-k1 次总复杂度 O(n×k)。当 n 很大、k 也很大时比如 n 10^5、k 5×10^4计算次数大约是 5×10^9 量级现代计算机一秒能跑 10^8 到 10^9 次简单运算这种规模基本就卡死了。暴力解法慢的本质是什么举个例子窗口从[1, 3, -1]滑到[3, -1, -3]重叠部分是[3, -1]。理论上第一个窗口已经比较过 3 和 -1 的大小关系第二个窗口可以直接复用这个结论——因为 3 比 -1 大对这两个元素的相对顺序而言新的最大值候选依然是 3如果它没过期的话。但暴力解法完全不记这个信息每次都把窗口里所有元素重新比一遍相当于每次移动都重算了一遍重叠部分的比较结果。这就像你在排队打饭每次队伍往里走一个人你就要从头到尾把所有排队的人重新数一遍身高找最高的——其实大部分人的身高你上次已经看过了。真正需要关注的只有新来的人有多高、队首的人有没有离开。2. 从 O(n×k) 到 O(n)单调队列为什么是标准答案2.1 用一个“候选者名单”来动态维护最大值优化的核心思路是维护一个始终有序的候选最大值名单窗口滑动时只做两个动作——新增一个候选项移除一个过期项。这个名单有这样一个性质排在越前面的元素值越大而且“存活时间”也越久。具体来说名单里保存的是数组元素的下标索引而不是元素值本身。为什么要存索引而不是存值因为光是知道“最大的数是 3”没用你没法判断这个 3 是不是已经滑出了窗口。而存了索引之后窗口的左边界是已知的只要索引小于左边界就说明这个值已经过期直接移除。比如窗口左边界是 2当前候选名单的队头索引是 1那就说明这个索引对应的元素已经在窗口左边外了过期了弹出。如果队头索引是 3还在窗口内那它依然是当前窗口的最大值候选。这个数据结构就是单调递减队列从队头到队尾元素对应的值依次递减。队头永远是当前窗口的最大值——因为只有最大的才有资格站队头其他的都在它后面“候补”。2.2 入队时为什么要从尾部“顶掉”小的这是单调队列最核心的一个操作也是很多人第一次看代码时最容易困惑的地方。先看规则每次新元素入队前把队尾所有值小于等于它的元素全部弹出。然后新元素从尾部入队。为什么要把队尾小的全部弹出因为窗口向右滑动新元素的“出生时间”一定晚于队列里任何已有的元素。对于任何一个已有的、值比新元素小的元素在新元素存活期间它永远不可能成为窗口最大值——新元素比它大且比它晚过期。所以它留在队列里没有任何意义只会白白增加队列的长度和比较次数。举例来说队列里现在存的索引对应的值是[7, 5]新来的元素值是 6。5 会被弹出7 保留。为什么 5 要被弹出因为 7 还在队列里最大值至少是 7就算以后 7 过期了还有 6 在5 依然排不上号。所以 5 是一个永远出不了头的“备胎”留着没用。这里有个细节很多人会写错弹出条件是“小于等于”而不是“小于”。为什么相等时也要弹出举个例子队列里有个值是 5新来的值也是 5。如果只弹出小于的那么队列里就会有连续两个 5。这两个 5 谁更适合当候选新来的 5 索引更大、过期更晚旧 5 能活的窗口新 5 都能活而且新 5 的值不比旧 5 小。所以旧 5 直接淘汰让新 5 顶替上去。这个细节在写代码时非常容易漏。2.3 窗口移动时的“过期弹出”和“结果记录”时机入队淘汰讲清楚了再看窗口移动的完整流程。假设窗口大小是 k遍历数组到位置 i 时流程分三步第一步执行入队前的淘汰把队尾所有值小于等于nums[i]的索引全部弹出。这保证了队列单调递减。第二步把索引 i 从队尾入队。第三步检查队头索引是否过期如果队头索引小于等于i - k说明它已经不在当前窗口内了弹出。第四步如果窗口已经形成即 i 大于等于 k-1把队头索引对应的值加入结果数组。为什么要先淘汰再入队而不是先入队再淘汰其实这两种写法都能实现但先淘汰再入队逻辑更清晰你先让队列保持单调递减的性质新元素进来之后队列依然有序如果先入队再淘汰新元素可能在队尾也可能在中间处理起来反而更容易乱。结果记录的时机也要注意窗口还没完全形成时队列里虽然已经维护了一部分元素但长度不够 k这时候记录最大值是没有意义的。所以要从 i k-1 开始才记录也就是第一个完整窗口的最后一个元素进入队列之后。我一开始写的时候容易把过期检查放在入队淘汰的前面这样也没错但要注意顺序别写反。更稳妥的写法是先淘汰队尾小数 → 入队 → 再淘汰队头过期 → 记录结果。四个步骤一次到位。3. 两种主流写法的完整实现与对比3.1 单调队列 双端队列的最终版本单调队列需要一个“两头都能操作”的数据结构队头要能弹出过期元素队尾要能弹出小值再入队新值。Python 的collections.deque、Java 的ArrayDeque、C 的std::deque都是专门干这个的。Python 实现如下from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] # 双端队列里存的是数组下标 dq deque() res [] for i in range(n): # 1. 维护单调递减队尾所有小于等于当前值的下标全部弹出 while dq and nums[dq[-1]] nums[i]: dq.pop() # 2. 当前下标入队 dq.append(i) # 3. 队头过期检查超过窗口范围就弹出去 if dq[0] i - k: dq.popleft() # 4. 窗口形成后记录队头对应的值 if i k - 1: res.append(nums[dq[0]]) return resJava 版本的核心逻辑完全一致class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length 0 || k 0) return new int[0]; int n nums.length; int[] res new int[n - k 1]; DequeInteger dq new ArrayDeque(); int idx 0; for (int i 0; i n; i) { while (!dq.isEmpty() nums[dq.peekLast()] nums[i]) { dq.pollLast(); } dq.offerLast(i); if (dq.peekFirst() i - k) { dq.pollFirst(); } if (i k - 1) { res[idx] nums[dq.peekFirst()]; } } return res; } }用题目给的例子验证一遍nums [1, 3, -1, -3, 5, 3, 6, 7]k 3。i0队列空1 入队队列[0]不满足记录条件i1nums[1]3队尾 1 被弹出因为 1 3索引 1 入队队列[1]不记录i2nums[2]-1-1 比 3 小直接入队队列[1, 2]窗口形成记录nums[1]3i3nums[3]-3入队队列[1, 2, 3]队头索引 1 大于 0未过期记录nums[1]3i4nums[4]5队尾 -3、-1、3 依次弹出索引 4 入队队列[4]记录nums[4]5i5nums[5]3入队队列[4, 5]记录nums[4]5i6nums[6]6队尾 3 弹出、5 弹出索引 6 入队队列[6]记录nums[6]6i7nums[7]7队尾 6 弹出索引 7 入队队列[7]记录nums[7]7最终结果[3, 3, 5, 5, 6, 7]和预期完全一致。整个过程里每个元素最多入队一次、出队一次均摊复杂度 O(n)空间复杂度 O(k)。3.2 优先队列堆也是一种解法但优劣要拎清除了单调队列这道题还有一个经典解法用最大堆。堆里存(值, 索引)的二元组每次窗口移动时把新元素入堆然后检查堆顶元素的索引是否还在窗口内如果过期就弹出一直到堆顶元素在窗口内它就是当前窗口的最大值。import heapq def maxSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] # 最大堆存 (-值, 索引)Python的heapq默认最小堆取负变成最大堆 heap [] res [] for i in range(n): heapq.heappush(heap, (-nums[i], i)) # 弹出所有过期的堆顶 while heap and heap[0][1] i - k: heapq.heappop(heap) if i k - 1: res.append(-heap[0][0]) return res这个解法的复杂度是 O(n log n)因为每次入堆、出堆都是 O(log k) 的操作。相比单调队列的 O(n)理论上堆解法要慢一些。但堆解法的代码更短逻辑更直接面试时如果一时没想到单调队列堆解法作为保底方案是完全够用的——至少不是暴力解。不过堆解法有个隐藏问题堆中会残留大量“已经过期的元素”每次取最大值前需要反复弹出过期的堆顶。最坏情况下堆的大小可能接近 n因为过期元素没有被及时清理。虽然均摊复杂度还是 O(n log n)但常数更大实际运行会比单调队列慢不少。如果数组是流式输入、窗口极大堆解法的性能劣势会更明显。从工程角度我更建议把单调队列作为首选方案。它不只是在 LeetCode 上跑得快在你处理实时数据流、维护滑动窗口统计指标时O(n) 的算法都是更可靠的选择。3.3 两种方案的对比总结维度单调队列双端队列优先队列最大堆时间复杂度O(n)每个元素进出队列各一次O(n log n)堆操作对数级空间复杂度O(k)队列里最多 k 个有效索引O(n)堆里可能残留过期元素代码量稍长但逻辑固定更短思路直观面试观感展示数据结构和优化意识合格的备选方案适用场景大规模数据、性能敏感场景快速实现、小规模数据面试时如果把两种方案都讲出来就说明你既懂优化又有务实兜底的能力这是很加分的。但最终手写代码时建议写单调队列版本——它才是这道题真正想考察的东西。4. 跑题的例子之外这些“易错点”和边界比题更难4.1 四个最容易写错的地方这道题提交记录里最常见的错误我整理成了一份速查表易错点错误写法正确逻辑原因队列存值还是存索引队列存nums的值必须存索引只有索引能判断是否过期值相同的情况下索引能区分新旧弹出条件写“”还是“”用判断队尾用判断队尾相等情况下新元素更新且更晚过期旧元素应该被淘汰记录结果的时机从 i0 开始记录从 ik-1 开始记录窗口长度小于 k 时队列头不一定是真正的窗口最大值过期判断的边界dq[0] i-kdq[0] i-k窗口左边界是 i-k1索引等于 i-k 的元素已经不在窗口里dq[0] i - k这个边界很多人会写错成。举个例子窗口大小 k3当前 i5 时窗口覆盖的索引是 3、4、5。左边界是 i-k1 3。队头索引如果是 3那么它是窗口内元素不能弹如果是 2已经过期要弹。判断条件dq[0] 2才能把索引为 2 的元素弹出去。如果你写成dq[0] 2索引 2 就永远弹不出去结果里就会出现“窗口外的数”。4.2 空数组、k1、kn 这些边界怎么处理边界测试是刷题中特别容易翻车的环节。我每次写完都会顺手跑几个特殊用例nums []直接返回[]。代码开头如果没有判空访问nums[0]就会报错。k 1窗口本身就是单元素结果就是原数组。单调队列的逻辑不受影响每个元素入队后立刻记录正常返回。k n只有一个完整窗口结果数组就是整个数组上长度为 n 的最大值也就是全局最大值。这时候过期检查基本不会触发逻辑依然正确。k n题目一般保证 k n但如果自己测试时不小心传了k n结果数组长度会是负数代码会崩。最好在开头加一行判断if k n: return []。这些边界情况不复杂但调试起来很麻烦。我的习惯是写代码时就在脑子里把 i0、ik-1、in-1 这三个特殊位置过一遍确保逻辑自洽。4.3 为什么不能用普通的 list 模拟队列有些初学者会想我用 Python 的list直接模拟队列不就行了pop(0)弹出队头pop()弹出队尾看起来都能实现。但这里有个性能陷阱Python 的 listpop(0)是 O(n) 的操作因为弹出第一个元素后后面的所有元素都要往前移动一位。如果你在循环里大量执行pop(0)总复杂度会重新退化到 O(n²)这道题你写了单调队列的“形”却没有得到单调队列的“神”。deque的popleft()是真正的 O(1) 操作因为双端队列在底层是用双向链表或者分块数组实现的两头增删都不涉及整体移动。Java 的ArrayDeque同理数组实现但用了环形结构头尾操作都是均摊 O(1)。这是刷题之外也很重要的工程经验选择数据结构不是看 API 像不像而是看操作的时间复杂度是否匹配你的算法设计。很多人背了“滑动窗口用双端队列”但不知道为什么必须是双端队列真正写的时候用错了容器还浑然不觉。5. 套路迁移这套结构能顺手解掉多少同类题5.1 从“最大值”到“最小值”一行改动的事单调队列这套模板把比较方向反过来就是滑动窗口最小值。把nums[dq[-1]] nums[i]改成nums[dq[-1]] nums[i]其他完全不用动。from collections import deque def minSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] dq deque() res [] for i in range(n): while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) if dq[0] i - k: dq.popleft() if i k - 1: res.append(nums[dq[0]]) return resLeetCode 239 的变体题其实很多比如求窗口内最大值的下标、求窗口中第二大的值、维护两个单调队列同时求最大值和最小值。通信和股票场景中常见的“移动平均线”配合“滚动极值”套路完全一样。掌握模板之后遇到任何“定长窗口极值”的题目都能直接套。5.2 更广的迁移单调栈和单调队列是兄弟单调队列的背后是“单调栈”思想的一种扩展。单调栈是只在一端栈顶维护单调性的数据结构典型应用是 LeetCode 84柱状图中最大的矩形和 LeetCode 496下一个更大元素。单调队列则把单调性维护扩展到了双端两端都能操作适合处理窗口滑动的场景。这两种数据结构共同的核心思想是利用你已经有的大小关系跳过那些“永远不可能成为答案”的候选者。柱状图最大矩形中一旦遇到一个比栈顶短的柱子短柱子右侧的矩形范围就确定了比它高的柱子都可以弹出并结算滑动窗口最大值中新元素比队尾大队尾就永远没机会成最大值直接弹出。如果你理解了这个“淘汰无用候选者”的思想你会发现它不只是算法题的道具在很多实际优化场景里都成立。比如实时排行榜维护、网络流量监控窗口的峰值计算、传感器数据流中的异常峰值检测本质上都是同一套逻辑维护一个动态更新、有过期机制的候选集合。5.3 一个进阶题绝对差不超过限制的最长连续子数组LeetCode 1438 是一道把单调队列用得很妙的题“绝对差不超过限制的最长连续子数组”。题目要求找最长连续子数组使得子数组内任意两个元素的差的绝对值不超过 limit。这题需要同时维护窗口内的最大值和最小值差值超过 limit 时就收缩窗口左边界。用两个单调队列分别存最大值候选和最小值候选左边界移动时同步清理两队中过期的索引。这里单调队列的价值在于你不需要每次收缩左边界后重新扫描整个窗口找最大最小值直接从两个队列头部取值就行均摊复杂度依然是 O(n)。这道题比 239 多了一个窗口长度不固定的变化但核心还是“双端队列维护窗口极值 索引过期清理”一通百通。如果你想检验自己是不是真的理解了单调队列可以拿 1438 练手。6. 面试现场怎么把一个解讲成加分项6.1 先讲朴素解再抛出优化思路展示思考过程面试官出这道题通常不只是想让你默写代码。他们更在意的是你面对问题时怎么思考能不能从暴力解出发找到重复计算的瓶颈再设计数据结构去消除冗余。一个比较稳健的答题节奏是第一句话先说暴力解“最直接的方法是每个窗口扫描一次复杂度 O(n×k)但这个在数据量大时不可接受。”第二句话指出瓶颈“相邻窗口有 k-1 个重叠元素暴力解把这些元素重复比较了。”第三句话抛出思路“我可以用一个单调递减的双端队列来维护候选最大值每次窗口移动时只做三个 O(1) 操作——新元素入队时淘汰队尾小于等于它的元素、检查队头是否过期、记录队头作为结果。”这样讲面试官能清晰看到你的思维链条而不是看到你背了一道题。即使他追问“为什么用双端队列而不是普通队列”你也能顺理成章地解释队尾要弹出小值、队头要弹出过期值普通队列只有一头能操作做不到。6.2 手写代码的节奏和注释细节面试手写代码时有几个习惯很加分先写注释说明队列里存什么// dq 存储数组下标对应值从队头到队尾递减。这一句话就能让面试官快速进入你的代码逻辑也能防止自己写着写着忘了队列的含义。变量名尽量直观。我见过有人用q、s、t这种单字母命名虽然代码短但别人读起来很费劲。用dqdeque和resresult就够了。在四个关键步骤前写上数字步骤注释// 1. 队尾维护单调递减 // 2. 新元素入队 // 3. 队头清理过期 // 4. 窗口完整后记录结果这种注释不是写给别人看的是帮你自己在写代码时保持步骤清晰。面试时边写边小声说思路也能让面试官跟上你的节奏。写完代码后一定要主动提出“我拿刚才的例子过一遍”。拿题目自带的示例跑一遍流程如果发现某一步不对当场调整。面试官更看重你调试问题的过程而不是一个完美的默写结果。6.3 追问环节的高频问题应对思路这道题的追问点其实很固定。提前准备一下答起来就很从容。问“为什么不用优先队列”答优先队列也可以代码更短但堆操作是 O(log k)整体 O(n log n)。单调队列能让每个元素最多进出一次达到 O(n)。面试场景我会先说堆是保底方案但单调队列在数据量更大时性能更优所以最终选它。问“如果数组是流式数据、不可预知长度呢”答这正好是单调队列更适合的场景。流式输入时窗口每来一个元素就处理一次单调队列均摊 O(1) 的维护成本非常适合实时处理。优先队列在流式场景下需要额外的惰性删除机制反而复杂。问“如果窗口大小是变化的呢”答单调队列里过期检查的条件从左边界固定变成动态更新即可队列结构本身不需要改变。这在 LeetCode 1438 这类题里已经体现了。问“如果要求的是窗口中第二大的值呢”答那单调队列就不够用了可能需要线段树或者平衡树。但面试到这里你其实可以坦诚说“这需要更高级的数据结构”并且话锋一转说出为什么单调队列只能维护极值——因为它淘汰了所有非极值候选第二大的信息已经被丢弃了。能说出这个边界本身就展示了你对数据结构的理解深度。我个人在面试中特别认同一个做法不要等面试官把追问抛完才回应而是自己主动把“为什么不用堆”“流式输入怎么办”这些问题作为补充讲出来。面试官每天面很多人听的都是差不多的答案你主动多讲一层就比其他人多展示一层深度。这道题你如果能把单调队列的“淘汰逻辑”和堆的“惰性删除”对比着讲已经能超过大多数候选人了。
阅读完成 · 觉得有帮助？
