打开力扣第239题看到“滑动窗口最大值”这七个字很多人第一反应是滑动窗口懂。最大值也懂。合在一起怎么就成困难题了点开官方题解看到“单调队列”四个字再扫一眼评论区一堆人喊着“劝退”“看不懂”果断关掉页面。如果你也是这个状态那这篇文章就是为你准备的。我会从最笨的暴力解法开始一步步演进到最优解把这道题彻彻底底讲透保证你看完能自己手写出来还能顺手应付面试官的追问。先说清楚这篇文章要解决什么给你一个数组和一个固定大小的窗口窗口每次往右动一格求每个窗口内的最大值。题目本身不复杂但背后的“单调队列”思想是很多公司面试的高频考点也跟后续一系列滑动窗口变种题直接挂钩。无论你是刚刷题的小白还是复习到瓶颈想查漏补缺的同学这篇都能给你一个完整的认知闭环。1. 先把题目老老实实掰开窗口、数组、最大值到底是什么1.1 题目原话与大白话翻译题目给了一个整数数组nums还有一个整数k表示滑动窗口的大小。窗口从数组的最左侧开始每次向右移动一位你要记录下每个窗口内的最大值最后返回由这些最大值组成的数组。大白话就是有一排数字排在那里你拿一个长度为k的框子从左往右框住k个数字每框一次就记下这k个数字里最大的那个然后框子右移一格重复操作直到框子到最右边。力扣239的经典示例是这样的输入: nums [1,3,-1,-3,5,3,6,7], k 3 输出: [3,3,5,5,6,7]拿这个例子自己手推一遍。窗口先框住[1,3,-1]最大值是3右移一位变成[3,-1,-3]最大值还是3再移变成[-1,-3,5]最大值是5接着[-3,5,3]最大值是5然后[5,3,6]最大值是6最后[3,6,7]最大值是7。所以结果是[3,3,5,5,6,7]。1.2 窗口到底是怎么“滑”的理解滑动窗口关键在于理解“滑”这个动作的本质。窗口本身没有动动的是窗口的边界。每次窗口向右移动一位发生的事情其实是两件左边出去一个元素右边进来一个元素。也就是说窗口内的内容是一个“先进先出”的过程这天然就是队列的结构。很多解法之所以难懂就是因为没有抓住这个队列本质。如果你心里始终绷着一根弦——窗口滑动等于队列弹出队头元素、压入队尾元素——那么后面讲单调队列时你就很容易跟上节奏。窗口滑动的次数也很容易算。一个长度为n的数组窗口大小为k一共会有n - k 1个窗口。比如8个元素窗口大小3就有8 - 3 1 6个窗口跟上面例子的输出长度完全吻合。1.3 边界情况别让窗口比数组还大很多小白在最开始写的时候会忽略一种情况如果k比数组长度还大或者k等于1怎么办如果k 1每个窗口只有一个元素最大值就是它自己结果数组和原数组一模一样。如果k n那根本形不成一个完整的窗口这种情况力扣的测试用例里一般不会出现题目隐含约束1 k nums.length但你在自己练习或面试手写时最好先跟面试官确认一下这个前提。边界条件是刷题中最容易被扣分的地方面试官很喜欢在这些细节上做文章。写代码前先把这些情况想清楚能省去很多debug时间。2. 暴力解先上手O(nk) 的笨办法也是解法2.1 每个窗口都扫一遍最大值我不建议一上来就啃最优解先写一个暴力解把题目的逻辑跑通比什么都重要。暴力的思路非常直白生成所有窗口对每个窗口遍历一遍找出最大值。class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; for (int i 0; i n - k; i) { int max nums[i]; for (int j i; j i k; j) { max Math.max(max, nums[j]); } ans[i] max; } return ans; } }Python版本写起来更简洁class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: n len(nums) ans [] for i in range(n - k 1): ans.append(max(nums[i:i k])) return ansPython这版可以说是最直观的翻译切窗口、求最大值、存结果。甚至不用自己写循环求max内置函数一步到位。2.2 暴力法的时间复杂度是多少分析复杂度外层循环有n - k 1个窗口每个窗口内要比较k个元素取最大值所以总比较次数是(n - k 1) * k时间复杂度就是O(nk)。空间复杂度除了输出结果数组我们只用了常数个临时变量所以是O(1)不计输出数组本身。2.3 暴力法的问题出在哪暴力法最大的问题在于窗口每滑动一次我们就把窗口内的元素全部重新看一遍完全没有利用上一次窗口的计算结果。举个例子。k3时第一个窗口是[1,3,-1]第二个窗口是[3,-1,-3]。这两个窗口有[3,-1]两个元素是重叠的我们在暴力解法里把这两个元素比较了两次。如果窗口很大比如k10000每次滑动只少了一个元素、多了一个元素但我们还是要重新比较一万个元素这显然浪费了大量已经算过的信息。这就是优化的突破口能不能找到一种数据结构让我们在上一个窗口的结果基础上只处理“出去一个、进来一个”这两个变化就能得到新窗口的最大值3. 聪明一点的思路用大顶堆维护“候选最大值”3.1 为什么想到堆如果你学过优先队列这时候脑子里会蹦出一个非常自然的想法维护一个大顶堆堆顶永远是当前窗口的最大值每次窗口滑动时把新元素插入堆中然后取堆顶就好了。等等取堆顶之前我们得先把已经滑出窗口的元素处理掉。比如第一个窗口最大值是3滑动之后1滑出去了如果1不在堆顶倒还好但如果滑出去的元素恰好是堆顶那堆顶就不能直接用了。3.2 懒删除让过期元素自己失效有一种技巧叫“懒删除”很实用。思路是我们不去主动删除堆中过期元素每次插入新元素后取堆顶时检查一下堆顶元素是否还在当前窗口范围内。如果不在就把它弹出直到堆顶元素是合法的为止。判断元素是否在窗口范围内靠的是下标。所以堆里存的应该是一个二元组(值, 下标)或者你把下标当成主键、值当成比较依据也行。只要堆顶的下标小于当前窗口的左边界i - k 1就说明它过气了弹出。class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; // 大顶堆按值降序排列值相同按下标升序 PriorityQueueint[] pq new PriorityQueue((a, b) - a[0] ! b[0] ? b[0] - a[0] : b[1] - a[1]); int[] ans new int[n - k 1]; int idx 0; for (int i 0; i n; i) { pq.offer(new int[]{nums[i], i}); // 窗口已经形成了 if (i k - 1) { // 弹出所有滑出窗口的过期元素 while (pq.peek()[1] i - k) { pq.poll(); } ans[idx] pq.peek()[0]; } } return ans; } }3.3 堆解法的复杂度与局限这样做的复杂度是多少每个元素至多入堆一次、出堆一次堆的插入和删除都是O(log n)所以总复杂度是O(n log n)。这个复杂度已经能应付绝大多数在线评测了但还不是最优。面试官如果继续问你“能不能做到 O(n)”你就需要祭出下一节的单调队列了。堆解法的局限也很明显堆中会残留大量已经过期的元素虽然在取堆顶时会被清掉但堆的规模峰值可能比实际窗口大得多。你可以理解成办公室里堆了一摞过期文件虽然每次只取最上面那份但柜子被塞得很满空间上不划算。而且O(log n)的堆操作虽然不慢但离“每个元素均摊 O(1)”还有距离。4. 单调队列O(n) 最优解也是本题的核心4.1 从“一个窗口内的候选者”想到队列现在进入正题。先思考一个问题窗口内所有元素都有必要成为“最大值候选者”吗假设当前窗口是[5, 3]然后新元素4进来了窗口变成[5, 3, 4]。请问3还有可能成为这个窗口的最大值吗不可能了因为4不仅比3大还比3晚滑出窗口——5走了之后4还在3走了之后4还在。无论从哪个角度看3都被4完全压制。再进一步窗口变成[3, 4, 2]3已经滑出去了4和2留下。2虽然比4小但它比4晚离开窗口存在一种可能将来4滑出窗口时2还没滑出届时2可能成为最大值。所以2必须保留。这就是单调队列的雏形维护一个队列里面只存放“有机会成为窗口最大值的元素”并且这些元素的值从左到右是严格递减的。队头永远是当前范围里最大的那个一旦队头的下标滑出窗口就把它扔掉下一个顶上。4.2 单调队列的维护规则我们用一个双端队列deque来存下标注意是下标不是值保证下标对应的元素值从队头到队尾单调递减。遍历数组时每一轮执行三步操作清理过期的队头队头下标如果小于i - k 1说明它已经不在当前窗口内从队头弹出。维护单调性从队尾开始往前看凡是比当前元素nums[i]小的元素统统弹出。因为它们又小又老在当前以及未来的窗口里都不可能成为最大值。压入当前元素下标把i放入队尾。当i k - 1时窗口已经形成此时队头下标对应的元素值就是当前窗口的最大值。为什么从队尾弹出比当前元素小的元素不会误删“未来可能的最大值”因为当前元素不但比它们大而且比它们晚离开窗口它们在任何情况下都不可能打赢当前元素。这是一种“窝里斗”的淘汰逻辑——既然后浪更猛前浪就没必要占着位置了。4.3 用示例完整走一遍拿nums [1,3,-1,-3,5,3,6,7], k 3手工模拟一遍你会彻底弄懂。i0队空。队列[0]值1i1值3。队尾是值113弹出。队列[1]值3i2值-1。队尾是值33-1保留。队列[1,2]值3,-1。窗口已形成队头下标1对应值3结果3。i3值-3。先检查队头下标1是否过期i-k11下标1没有过期等于左边界保留。队尾值-1-1-3保留。队列[1,2,3]值3,-1,-3。队头下标1对应值3结果3。i4值5。检查队头下标1左边界4-312所以下标1过期弹出。现在队列[2,3]。再维护单调性队尾值-35-3弹出队尾值-15-1弹出。队列[4]。队头下标4对应值5结果5。i5值3。检查队头下标4左边界3没有过期。队尾值553保留。队列[4,5]。队头值5结果5。i6值6。检查队头下标4左边界4没有过期。队尾值363弹出队尾值565弹出。队列[6]。队头值6结果6。i7值7。检查队头下标6左边界5没有过期。队尾值676弹出。队列[7]。队头值7结果7。最终结果[3,3,5,5,6,7]完全正确。走一遍这个过程你就能直观感受到“过期队头被清掉小元素被新元素吃掉”这两个动作是怎么配合的。4.4 完整代码Java、Python、CJava版本class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; DequeInteger deque new ArrayDeque(); int[] ans new int[n - k 1]; int idx 0; for (int i 0; i n; i) { // 1. 清理过期队头 while (!deque.isEmpty() deque.peekFirst() i - k) { deque.pollFirst(); } // 2. 维护单调递减弹出所有比当前元素小的队尾 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. 当前下标入队 deque.offerLast(i); // 4. 窗口形成后收集结果 if (i k - 1) { ans[idx] nums[deque.peekFirst()]; } } return ans; } }Python版本from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: dq deque() ans [] for i, x in enumerate(nums): # 清理过期队头 while dq and dq[0] i - k: dq.popleft() # 维护单调递减 while dq and nums[dq[-1]] x: dq.pop() dq.append(i) # 窗口形成后收集结果 if i k - 1: ans.append(nums[dq[0]]) return ansC版本class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; vectorint ans; for (int i 0; i nums.size(); i) { while (!dq.empty() dq.front() i - k) { dq.pop_front(); } while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); if (i k - 1) { ans.push_back(nums[dq.front()]); } } return ans; } };三个语言的核心逻辑完全一致。用你熟悉的语言把代码背熟理解每一步在干什么比死记硬背要可靠得多。复杂度分析每个元素最多入队一次、出队一次所以总时间是O(n)。空间上队列最大不会超过窗口大小k所以空间复杂度是O(k)。5. 写代码时最容易踩的坑5.1 队列里存的是下标不是值新手最容易犯的错直接在队列里存值然后比较大小。为什么必须存下标因为你要判断一个元素是不是滑出了窗口靠的是它的位置而不是它的大小。存值的话过期检查就无从谈起。一旦你写的是dq.peekLast() nums[i]而不是nums[dq.peekLast()] nums[i]基本就是拿下标跟值比大小编译可能都过不去。5.2 过期检查一定放在最前面很多人照着模板写结果把顺序搞反了先维护单调性再清理过期队头。这会引发一个隐蔽的bug——如果队头已经过期了但它恰好是队列里最大的元素你维护单调性时拿它与新元素比较它可能被当成“合法候选”保留最后输出一个已经滑出窗口的元素。记住先清理过期队头再维护单调性最后入队。三步顺序是固定的不要随意调换。5.3 结果收集的时机窗口还没形成时不要输出窗口是逐步形成的。在i从0增长到k-2的过程中窗口还没满这时候队头虽然也有值但它不是完整窗口的最大值直接输出会导致结果数组多出错误数据。正确做法是等到i k - 1再开始收集答案。这个条件等价于“当前下标已经足够撑起一个完整窗口”。5.4 语言实现细节Java里ArrayDeque不允许插入null所以队列里存下标不会受影响。使用peekFirst()和peekLast()时要确保队列非空所以while循环里的!deque.isEmpty()条件一定不能漏。Python的deque支持dq[0]、dq[-1]这样的索引访问这是双端队列的特性用起来非常顺手。但注意dq.pop()默认从右边弹出dq.popleft()从左边弹出别搞混。C 的deque同样支持front()、back()、push_back()、pop_front()、pop_back()逻辑跟另外两种语言完全一致。5.5 一个值得注意的边界窗口内所有元素都一样如果数组是[1,1,1,1,1]k3会怎样按照规则第2步的弹出条件是nums[队尾] nums[i]也就是说相等的元素也会被弹出。这是有意为之前面的1和后面的1一样大但后面的1更晚过期所以保留后面的更优。如果你把弹出条件改成虽然这道题也能通过因为相等值不影响最大值结果但在某些变种题里会出问题。统一写成才是标准答案。6. 从239出发滑动窗口家族的变形题与真实场景6.1 滑动窗口最小值换个比较方向就好力扣没有直接对应“滑动窗口最小值”的题目但很多公司面试会让手写。思路一模一样只需要把“弹出所有比当前元素小的”改成“弹出所有比当前元素大的”保持队列从头到尾递增队头就是最小值。6.2 单调队列和单调栈的关系很多初学者分不清单调队列和单调栈。简单说栈是“后进先出”队列是“先进先出”。处理滑动窗口时窗口本身有“先进先出”的淘汰机制所以要队列处理“下一个更大元素”“接雨水”这类只看左侧或右侧的题目时用的是栈。它们的底层思想都是“维护单调性”只是数据结构和应用场景不同。6.3 滑动窗口在真实业务场景的影子别觉得这题只是面试八股。滑动窗口最大值在真实世界里应用很广。比如实时监控系统里统计最近一分钟内某项指标的最大值比如音视频处理里滑动窗口滤波要在连续帧中取邻域最大值再比如电商大促期间实时统计最近N分钟的最高订单金额底层逻辑都是滑动窗口。你在这道题里练熟的单调队列党直接能迁移到海量数据流处理的思想框架中——只是工程上会用更大的堆或专用数据结构但原理一脉相承。6.4 刷题建议怎么才算真正掌握这一题我自己的经验是一道题真正掌握的标准是“三个小时后再写一遍不看任何参考能一次通过”。具体到239建议按这个步骤来读完本文后立刻合上电脑在纸上把示例的手推过程画一遍。自己用熟悉的语言写一版单调队列跑过测试用例。第二天不看书重新写一遍重点检查5.1到5.3的三个坑有没有犯。顺手把滑动窗口最小值、滑动窗口中位数这两个变形题做掉巩固思路。6.5 更多变体除了最小值还有滑动窗口中位数用两个堆、滑动窗口平均值前缀和或单调队列累加、滑动窗口最大值且支持双端扩展等变体。掌握了239的核心思想后这些题目做起来会轻松很多。以后再遇到“窗口最值”的题脑子里第一反应应该是能不能用单调队列把无效元素淘汰掉我个人刷完239后最大的收获其实不是背会了单调队列的代码而是建立了一种“淘汰无用候选者”的直觉——很多算法题的优化本质上都是把永远不可能被选中的元素提前扔掉。带着这个视角再去看其他题目你会觉得整个算法世界都通透了。