解法)
刷题的朋友应该都听过力扣239这道题就算没刷过也大概率在面经里见过它的大名。滑动窗口最大值一道标着Hard、但实际思路并不算难懂的问题却卡住了大量从暴力解法往高效解法过渡的人。我当年第一次做这道题上来就是两层循环跑是跑通了一提交直接超时那会儿才意识到这题真正想考的不是“能不能算出答案”而是“能不能在线性时间里算出答案”。这篇内容我按“小白也能完全听懂”的标准来写不跳过任何一步推导不默认你已经懂单调队列也不堆一堆看似高深实则没用的术语。你只需要知道数组是什么、for循环怎么用就能完整跟下来。等你看完这篇再去把代码手写一遍滑动窗口这类题基本就通了一半。1. 先把题目看明白滑动窗口到底在求什么1.1 题目描述与手动模拟给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位返回滑动窗口中的最大值。看一个具体例子。假设数组是[1, 3, -1, -3, 5, 3, 6, 7]k 3我们把窗口从左往右滑窗口位置 0[1, 3, -1]最大值是3窗口位置 1[3, -1, -3]最大值是3窗口位置 2[-1, -3, 5]最大值是5窗口位置 3[-3, 5, 3]最大值是5窗口位置 4[5, 3, 6]最大值是6窗口位置 5[3, 6, 7]最大值是7所以输出就是[3, 3, 5, 5, 6, 7]。注意一个细节窗口每次只挪一格窗口内的元素变化其实很小——只出去一个最左边的只进来一个新元素。这个“大部分元素没变”的特点就是我们可以优化算法的突破口。1.2 小白第一反应暴力解法为什么不灵看到这个题目绝大多数人的第一反应就是两层循环外层遍历窗口的起始位置内层遍历窗口里的每一个元素找最大值。def maxSlidingWindow(nums, k): n len(nums) result [] for i in range(n - k 1): window_max nums[i] for j in range(i, i k): window_max max(window_max, nums[j]) result.append(window_max) return result这段代码逻辑一点问题没有答案完全正确。但它的时间复杂度是 O(n × k)外层有n-k1个窗口每个窗口里要比较k次。这样有什么问题我们来算一笔账假设nums长度是 10 万k是 5 万那么总共要做约50001 × 50000 ≈ 25亿次比较。25 亿次就算每次操作再快在大多数在线评测系统里也妥妥超时。所以这题虽然标着 Hard但难的不是“想出暴力解法”而是“想出比暴力解法更聪明的做法”。这道题本质上考的是你能不能利用窗口滑动的规律把重复的比较省掉。面试官想看到的是你对单调队列这种数据结构的理解和应用能力。2. 核心思路拆解从“重复扫描”到“滚动维护”2.1 一个生活化类比窗口像一条移动的队伍我们先别急着看代码先想通一个问题一个窗口从旧位置移到新位置里面发生了什么[1, 3, -1]变成[3, -1, -3]其实就是1从窗口里出去了-3进到窗口里了而3和-1这两个元素两个窗口里都在。如果你每次窗口移动都重新扫描一遍窗口里所有元素那对3和-1来说其实被重复比较了很多次。怎么避免这种重复答案就是把这k个元素按某种方式“维护”起来窗口动一下我们就更新一下这个“维护结构”并且能在 O(1) 时间内拿到最大值。你可以想象这样一个场景窗口里站着一排人你要随时知道谁最高。每次队伍只变一点最左边的人出队最右边进一个新人。那你有没有必要每次重新量所有人的身高其实没必要。你只需要记住当前最高的人是谁然后处理“出去的人”和“进来的人”就行了。不过这里有一个麻烦如果出去的人刚好就是当前最高的人那你就需要一个“替补”——也就是剩余人里的最高者。怎么快速找到替补这就是单调队列要解决的核心问题。2.2 单调队列登场队列里存下标而不是值解决这个问题我们需要一个数据结构双端队列deque。它的特点是两头都能进能出Python 里有collections.dequeC 里有std::dequeJava 里有ArrayDeque。关键来了我们要维护一个“从队头到队尾对应数值严格递减”的队列。什么意思就是队头的元素一定是当前队列里数值最大的而且越往队尾数值越小。这个队列有两个操作新元素入队前先把队尾所有比它小的元素从队尾弹出然后它再从队尾入队。为什么因为那些比新元素小、而且位置还靠前的元素在窗口后续滑动的过程中永远不可能成为最大值了——新元素既比它们大又比它们晚离开窗口它们留着没有任何意义。队头如果已经滑出当前窗口就把它从队头弹出。因为它的“有效期”已经过了。这里特别要强调一句队列里存的是数组下标index不是值。这一句话值五分面试官听了会眼睛一亮因为你直接点出了这个算法最核心的设计选择。存下标一方面能够通过nums[下标]拿到值另一方面还能用来判断元素是否已经滑出了窗口。如果你只存值窗口边界一变化你根本不知道这个值还属不属于当前窗口逻辑直接崩盘。2.3 每一次窗口滑动的三步操作假设我们已经构建好了滑动窗口现在窗口每次右移一格我们要做的事情非常固定就三步清理队尾只要队尾对应的数小于等于当前新元素就把队尾弹出。这一步保证队列单调递减。新元素入队把当前元素的下标放到队尾。清理队头如果队头下标已经不在当前窗口范围内也就是队头下标 i - k就把队头弹出。这一步保证队头永远是当前窗口内某个元素的下标。做完这三步队头下标对应的数就是当前窗口的最大值。为什么队头就是最大值因为队列是单调递减的队头永远最大。为什么它一定在当前窗口内因为第 3 步把所有过期的下标都已经请出去了。这里再说得细一点第 3 步的清理队头放在入队之后会不会出问题其实放在入队之后是刻意的。因为如果你先清理队头再入队新元素那么一种特殊情况新元素入队后它自己可能成为队头而它的下标可能比窗口左边界还小——这种情况发生在窗口还没完全展开、也就是 i 还小于 k-1 的时候。但如果先入队再清理就统一了逻辑代码更简单。实际写的时候两步顺序必须固定不然边界条件会绕晕你。还有一步容易被人忽略窗口还没收集满 k 个元素之前i - k 1 0也就是说当前窗口不够长不能输出答案。需要等i k - 1之后每次滑动完窗口才能把队头对应的值加入结果数组。很多新手在这里漏了条件导致结果数组里混进了一些“半个窗口”的答案。3. 代码实现从伪代码到一行行讲透3.1 Python 版完整代码与逐行解析话不多说先上完整代码from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] dq deque() result [] 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. 窗口满 k 个后开始记录结果 if i k - 1: result.append(nums[dq[0]]) return result逐行拆解一下关键逻辑while dq and nums[dq[-1]] nums[i]这里用而不是。为什么如果新元素和队尾元素相等把队尾弹出是安全的因为新元素下标更大会在窗口中存留更久用新元素替代旧元素更合理。这就是“同值时保留更靠右的那个”的策略能避免队里残留一堆永远用不上的相等元素。dq.append(i)把当前元素的下标加入队尾。if dq[0] i - k这个判断是核心中的核心。假设当前位置是i窗口大小是k那么当前窗口的左边界就是i - k 1。如果一个元素的下标 i - k说明它已经滑出了窗口左边界不再属于窗口范围。注意这里等号dq[0] i - k时这个元素刚好在窗口左边界再往左一格已经出去了。举个例子i 5k 3窗口覆盖[3, 4, 5]下标2已经滑出而2 5 - 3所以条件是。if i k - 1窗口固定大小是 k当索引从 0 数到k-1时第一个完整的窗口才出现。比如k 3那么i 0, 1, 2加起来是 3 个元素所以i 2时第一个窗口完成。之后每走一步就有一个新的完整窗口。3.2 C 版实现不同语言同一套路很多刷题的朋友用的是 C这里也给出对应版本。逻辑完全一样只是语法不同class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); vectorint result; dequeint dq; for (int i 0; i n; i) { // 维护单调递减队列 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 移除滑出窗口的队头 if (dq.front() i - k) { dq.pop_front(); } // 窗口满 k 后记录答案 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };如果你用的是 Java 或者 Go思路完全一致换一下容器类型就行Java 用ArrayDequeIntegerGo 直接用切片头尾操作模拟双端队列。核心思想与语言无关。3.3 为什么队列里存下标而不是直接存值这个问题我前面提过但值得展开再讲一遍因为它真的很重要。假设我们队列里直接存值比如队列现在是[5, 3]窗口要向右滑一格出去的是5进来的是4。这时你怎么判断5是不是已经出窗口了你不知道。因为这个值在数组里可能出现了多次也可能确实只出现了一次但光看值你无法判断。而如果存的是下标一切就非常清爽每次窗口滑动我只需要看队头的下标是否小于当前窗口左边界就知道它在不在窗口里。存下标相当于同时携带了“值”和“位置”两种信息判断过期、比较大小都靠它两全其美。再举一个极端例子nums [2, 2, 2, 2, 2]k 2。如果你存值队里一个2和另一个2根本无法区分你根本不知道要走的是哪个。但如果你存下标队头下标是0当i 2时0 2 - 2成立知道它该走了完美。这个例子直观地说明了为什么“只存值”是行不通的。3.4 复杂度分析为什么它是 O(n)时间复杂度每个元素最多入队一次、出队一次。入队是在处理到它的时候出队有两种可能——因为比它大的新元素来了而被从队尾弹出或者因为滑出窗口而被从队头弹出。无论是哪种每个元素都只会出队一次。所以循环虽然看起来是嵌套的while加for但所有while操作的总次数是 O(n)整体复杂度就是 O(n)。空间复杂度队列最多同时存k个元素所以是 O(k)。如果把结果数组算进去输出数组本身就是必须的不算额外空间。对比一下暴力法的 O(n × k)这个提升是巨大的。当n 100000, k 50000时暴力法要比较约 25 亿次单调队列只要约 10 万次操作差距肉眼可见。4. 我刷这道题踩过的坑常见问题与排查实录4.1 坑一队列里存值导致窗口过期判断失效这是我见过的初学者最容易犯的错误包括我自己第一次写也没逃过。很多人理解了“维护递减队列”之后直接把值扔进队列里代码长这样dq deque() for i in range(n): while dq and dq[-1] nums[i]: dq.pop() dq.append(nums[i]) if i k and dq[0] nums[i - k]: # 试图用值判断过期 dq.popleft() if i k - 1: result.append(dq[0])这个if i k and dq[0] nums[i - k]看起来很合理但实际一跑就会出错。原因是最开始说的如果窗口出去的那个元素并不是当前队头这个判断根本不会触发它直接就把一个已经该出队的元素留在队列里了。更麻烦的是即使它等于队头的值也可能因为重复元素而误判。所以不要尝试用值去判断过期一定要存下标。4.2 坑二弹出条件用了导致相同元素堆积很多人会纠结nums[dq[-1]] nums[i]这里的等号要不要加。如果你写的是会怎样考虑nums [4, 4, 4, 4]k 2i0队列[0]i1队尾4 4为假因为用的是队列变成[0, 1]结果输出nums[0] 4i2队尾4 4为假队列变成[0, 1, 2]清理队头0 0成立弹出0队列[1, 2]结果输出nums[1] 4i3同理看起来结果没毛病那和的区别到底在哪主要在于队列长度。用时相等元素不会被弹出队列可能会同时保留多个相同最大值的下标队列最长可能超过 k但不会影响正确性只是浪费了一点点空间。用时相同元素会互相顶掉队列更短更高效。两者的结果都一样但推荐用因为队列更精简逻辑也更干净。4.3 坑三窗口过期判断写成了而不是这个更隐蔽。假设k 3当前i 3窗口范围应该是下标[1, 2, 3]。如果队头下标是0它显然已经不在窗口里了。0 3 - 3 0成立所以我们应该用把它弹出去。如果你写成0 0不成立这个已经过期的下标就会留在队列里并且很有可能会被当成最大值输出直接导致答案错误。一句话记法判断过期时用i - k这个边界值已经属于“窗口外”了。4.4 坑四用 Python 的 list 模拟双端队列新手容易图省事直接用list当作队列dq [] ... dq.pop(0) # 弹出队头在 Python 里list.pop(0)是 O(n) 操作因为要移动后面所有元素。如果你在循环里反复pop(0)整体复杂度直接退化到 O(n²)数据规模一上来照样超时。所以务必用collections.deque或者list 头尾双指针手动模拟。这里分享一个面试时能加分的技巧其实你也可以不用 deque而是用一个普通数组配合两个指针来模拟代码看起来更底层展示你对“双端队列本质就是数组加头尾指针”的理解。但日常做题还是deque最方便。4.5 面试官追问为什么不用大顶堆这是一个非常高频的追问。很多人第一反应是“用堆不也能拿到最大值吗”确实大顶堆也可以维护窗口内最大值但有一个麻烦堆不方便删除“滑出窗口的那个特定元素”。标准做法是“延迟删除”——也就是把元素存入堆时连同下标一起存每次取堆顶时不停弹出那些下标已经超出窗口的元素直到堆顶合法。这个写法也能过时间复杂度是 O(n log k)。因为每个元素入堆一次、出堆一次每次都是 O(log k)。而单调队列能做到均摊 O(n)比堆更快而且实现也更简洁。所以面试官更想听到的答案就是在滑动窗口这种“先进先出”的场景下单调队列是更优解。补充一个边界处理如果k 1每个窗口只有一个元素答案就是数组本身单调队列也能正常处理不需要特判。如果k n其实整个数组就一个窗口直接返回全数组最大值即可但单调队列的逻辑也不需要特判因为它会等i n-1时输出唯一的答案。唯一需要特判的是nums为空的情况。5. 举一反三这类题背后的通用套路5.1 什么样的问题适合用单调队列刷题多了你会发现“滑动窗口最大值”只是单调队列的一个典型代表。这个算法的适用场景可以总结为三个关键词滑动窗口、最值、先进先出。比如这一类问题求每个长度为 k 的子数组的最小值把单调递减换成单调递增队头最小就行代码几乎一样。求滑动窗口内的中位数这就不能直接用单调队列了通常需要两个堆或者有序结构但思路仍然是“维护窗口内的数据有序”。求满足某种约束的最长连续子数组比如“绝对差不超过 limit 的最长连续子数组”这题需要同时维护一个最大值单调队列和最小值单调队列然后移动窗口左边界是 239 题的直接升级版。当你拿到一个新题时可以先自我提问三连是否有连续的“窗口”窗口是否只向右滑动是否要实时获取窗口内某种极值信息如果三个答案都是“是”那第一时间想到单调队列准没错。这个思维模式能帮你在面试时候快速定位到正确的解法方向。5.2 相似题对比与联系力扣 239 的兄弟题们很多题表面长得不一样内核其实一模一样。我刷到过几道和 239 高度相关的题给你整理一下方便串联记忆题目核心要求用到的方法与 239 的关系力扣 239 滑动窗口最大值每个窗口的最大值单调递减队列本体剑指 Offer 59-I 滑动窗口的最大值同上同上完全一样力扣 1438 绝对差不超过限制的最长连续子数组维护窗口内最大最小值差两个单调队列239 的升级版力扣 1696 跳跃游戏 VI每个位置可从前面 k 步内转移单调队列优化 DP单调队列用于取前 k 个位置的最大转移值力扣 862 和至少为 K 的最短子数组前缀和 窗口约束单调队列维护索引思想同源但目标不同特别是 1696很多初学者根本想不到它居然也能用单调队列优化。它的本质是dp[i] nums[i] max(dp[i-k..i-1])那max(dp[i-k..i-1])本身就是一个滑动窗口最大值问题。一旦你看穿这层整个题就变得非常清晰。5.3 面试进阶流式输入怎么处理面试官还有一种问法会直接改变题目输入模型如果数组不是一次性全部给到而是一个一个地流式输入你还能用单调队列吗答案是可以而且单调队列天然适合流式处理。你不需要知道整个数组长什么样只需要在每来一个新元素时做那三步操作然后从队头拿答案。对i小于k-1的时候“窗口不够长”你可以先不输出或者输出空值等凑满 k 个再开始产生结果。这种场景对应到工程实践上就是日志系统、实时监控、股票行情里的“最近 k 条数据的最大值”需求。所以刷题并不是纯应试这道题的思路在实际系统中同样有用。理解到这一层你对单调队列的理解就超越“背模板”的水平了。另外我再分享一个调试小技巧如果你发现自己写的程序答案不对先在每次入队、出队操作后打印整个队列里的下标和对应值一步一步对照手算过程找出是哪一步的弹出条件写错了。我当年就是这么定位到自己把写成的。这一招比盯着代码看半天管用得多真的。力扣 239 这道题我第一次刷完只是“看懂了答案”真正理解是后来的事。当时我对着代码在心里跑了七八个用例把队列的每一步变化都写在纸上才彻底想明白“为什么队头一定是最大值”“为什么每个元素只会进出一次”。所以如果你现在还有点懵别急着背代码拿笔在纸上手动模拟一遍模拟完你会发现自己突然就通了。这个习惯也让我在后面刷单调队列优化的 DP 题时少走了很多弯路。
力扣239滑动窗口最大值：从暴力到单调队列的O(n)解法
刷题的朋友应该都听过力扣239这道题就算没刷过也大概率在面经里见过它的大名。滑动窗口最大值一道标着Hard、但实际思路并不算难懂的问题却卡住了大量从暴力解法往高效解法过渡的人。我当年第一次做这道题上来就是两层循环跑是跑通了一提交直接超时那会儿才意识到这题真正想考的不是“能不能算出答案”而是“能不能在线性时间里算出答案”。这篇内容我按“小白也能完全听懂”的标准来写不跳过任何一步推导不默认你已经懂单调队列也不堆一堆看似高深实则没用的术语。你只需要知道数组是什么、for循环怎么用就能完整跟下来。等你看完这篇再去把代码手写一遍滑动窗口这类题基本就通了一半。1. 先把题目看明白滑动窗口到底在求什么1.1 题目描述与手动模拟给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位返回滑动窗口中的最大值。看一个具体例子。假设数组是[1, 3, -1, -3, 5, 3, 6, 7]k 3我们把窗口从左往右滑窗口位置 0[1, 3, -1]最大值是3窗口位置 1[3, -1, -3]最大值是3窗口位置 2[-1, -3, 5]最大值是5窗口位置 3[-3, 5, 3]最大值是5窗口位置 4[5, 3, 6]最大值是6窗口位置 5[3, 6, 7]最大值是7所以输出就是[3, 3, 5, 5, 6, 7]。注意一个细节窗口每次只挪一格窗口内的元素变化其实很小——只出去一个最左边的只进来一个新元素。这个“大部分元素没变”的特点就是我们可以优化算法的突破口。1.2 小白第一反应暴力解法为什么不灵看到这个题目绝大多数人的第一反应就是两层循环外层遍历窗口的起始位置内层遍历窗口里的每一个元素找最大值。def maxSlidingWindow(nums, k): n len(nums) result [] for i in range(n - k 1): window_max nums[i] for j in range(i, i k): window_max max(window_max, nums[j]) result.append(window_max) return result这段代码逻辑一点问题没有答案完全正确。但它的时间复杂度是 O(n × k)外层有n-k1个窗口每个窗口里要比较k次。这样有什么问题我们来算一笔账假设nums长度是 10 万k是 5 万那么总共要做约50001 × 50000 ≈ 25亿次比较。25 亿次就算每次操作再快在大多数在线评测系统里也妥妥超时。所以这题虽然标着 Hard但难的不是“想出暴力解法”而是“想出比暴力解法更聪明的做法”。这道题本质上考的是你能不能利用窗口滑动的规律把重复的比较省掉。面试官想看到的是你对单调队列这种数据结构的理解和应用能力。2. 核心思路拆解从“重复扫描”到“滚动维护”2.1 一个生活化类比窗口像一条移动的队伍我们先别急着看代码先想通一个问题一个窗口从旧位置移到新位置里面发生了什么[1, 3, -1]变成[3, -1, -3]其实就是1从窗口里出去了-3进到窗口里了而3和-1这两个元素两个窗口里都在。如果你每次窗口移动都重新扫描一遍窗口里所有元素那对3和-1来说其实被重复比较了很多次。怎么避免这种重复答案就是把这k个元素按某种方式“维护”起来窗口动一下我们就更新一下这个“维护结构”并且能在 O(1) 时间内拿到最大值。你可以想象这样一个场景窗口里站着一排人你要随时知道谁最高。每次队伍只变一点最左边的人出队最右边进一个新人。那你有没有必要每次重新量所有人的身高其实没必要。你只需要记住当前最高的人是谁然后处理“出去的人”和“进来的人”就行了。不过这里有一个麻烦如果出去的人刚好就是当前最高的人那你就需要一个“替补”——也就是剩余人里的最高者。怎么快速找到替补这就是单调队列要解决的核心问题。2.2 单调队列登场队列里存下标而不是值解决这个问题我们需要一个数据结构双端队列deque。它的特点是两头都能进能出Python 里有collections.dequeC 里有std::dequeJava 里有ArrayDeque。关键来了我们要维护一个“从队头到队尾对应数值严格递减”的队列。什么意思就是队头的元素一定是当前队列里数值最大的而且越往队尾数值越小。这个队列有两个操作新元素入队前先把队尾所有比它小的元素从队尾弹出然后它再从队尾入队。为什么因为那些比新元素小、而且位置还靠前的元素在窗口后续滑动的过程中永远不可能成为最大值了——新元素既比它们大又比它们晚离开窗口它们留着没有任何意义。队头如果已经滑出当前窗口就把它从队头弹出。因为它的“有效期”已经过了。这里特别要强调一句队列里存的是数组下标index不是值。这一句话值五分面试官听了会眼睛一亮因为你直接点出了这个算法最核心的设计选择。存下标一方面能够通过nums[下标]拿到值另一方面还能用来判断元素是否已经滑出了窗口。如果你只存值窗口边界一变化你根本不知道这个值还属不属于当前窗口逻辑直接崩盘。2.3 每一次窗口滑动的三步操作假设我们已经构建好了滑动窗口现在窗口每次右移一格我们要做的事情非常固定就三步清理队尾只要队尾对应的数小于等于当前新元素就把队尾弹出。这一步保证队列单调递减。新元素入队把当前元素的下标放到队尾。清理队头如果队头下标已经不在当前窗口范围内也就是队头下标 i - k就把队头弹出。这一步保证队头永远是当前窗口内某个元素的下标。做完这三步队头下标对应的数就是当前窗口的最大值。为什么队头就是最大值因为队列是单调递减的队头永远最大。为什么它一定在当前窗口内因为第 3 步把所有过期的下标都已经请出去了。这里再说得细一点第 3 步的清理队头放在入队之后会不会出问题其实放在入队之后是刻意的。因为如果你先清理队头再入队新元素那么一种特殊情况新元素入队后它自己可能成为队头而它的下标可能比窗口左边界还小——这种情况发生在窗口还没完全展开、也就是 i 还小于 k-1 的时候。但如果先入队再清理就统一了逻辑代码更简单。实际写的时候两步顺序必须固定不然边界条件会绕晕你。还有一步容易被人忽略窗口还没收集满 k 个元素之前i - k 1 0也就是说当前窗口不够长不能输出答案。需要等i k - 1之后每次滑动完窗口才能把队头对应的值加入结果数组。很多新手在这里漏了条件导致结果数组里混进了一些“半个窗口”的答案。3. 代码实现从伪代码到一行行讲透3.1 Python 版完整代码与逐行解析话不多说先上完整代码from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] dq deque() result [] 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. 窗口满 k 个后开始记录结果 if i k - 1: result.append(nums[dq[0]]) return result逐行拆解一下关键逻辑while dq and nums[dq[-1]] nums[i]这里用而不是。为什么如果新元素和队尾元素相等把队尾弹出是安全的因为新元素下标更大会在窗口中存留更久用新元素替代旧元素更合理。这就是“同值时保留更靠右的那个”的策略能避免队里残留一堆永远用不上的相等元素。dq.append(i)把当前元素的下标加入队尾。if dq[0] i - k这个判断是核心中的核心。假设当前位置是i窗口大小是k那么当前窗口的左边界就是i - k 1。如果一个元素的下标 i - k说明它已经滑出了窗口左边界不再属于窗口范围。注意这里等号dq[0] i - k时这个元素刚好在窗口左边界再往左一格已经出去了。举个例子i 5k 3窗口覆盖[3, 4, 5]下标2已经滑出而2 5 - 3所以条件是。if i k - 1窗口固定大小是 k当索引从 0 数到k-1时第一个完整的窗口才出现。比如k 3那么i 0, 1, 2加起来是 3 个元素所以i 2时第一个窗口完成。之后每走一步就有一个新的完整窗口。3.2 C 版实现不同语言同一套路很多刷题的朋友用的是 C这里也给出对应版本。逻辑完全一样只是语法不同class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); vectorint result; dequeint dq; for (int i 0; i n; i) { // 维护单调递减队列 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 移除滑出窗口的队头 if (dq.front() i - k) { dq.pop_front(); } // 窗口满 k 后记录答案 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };如果你用的是 Java 或者 Go思路完全一致换一下容器类型就行Java 用ArrayDequeIntegerGo 直接用切片头尾操作模拟双端队列。核心思想与语言无关。3.3 为什么队列里存下标而不是直接存值这个问题我前面提过但值得展开再讲一遍因为它真的很重要。假设我们队列里直接存值比如队列现在是[5, 3]窗口要向右滑一格出去的是5进来的是4。这时你怎么判断5是不是已经出窗口了你不知道。因为这个值在数组里可能出现了多次也可能确实只出现了一次但光看值你无法判断。而如果存的是下标一切就非常清爽每次窗口滑动我只需要看队头的下标是否小于当前窗口左边界就知道它在不在窗口里。存下标相当于同时携带了“值”和“位置”两种信息判断过期、比较大小都靠它两全其美。再举一个极端例子nums [2, 2, 2, 2, 2]k 2。如果你存值队里一个2和另一个2根本无法区分你根本不知道要走的是哪个。但如果你存下标队头下标是0当i 2时0 2 - 2成立知道它该走了完美。这个例子直观地说明了为什么“只存值”是行不通的。3.4 复杂度分析为什么它是 O(n)时间复杂度每个元素最多入队一次、出队一次。入队是在处理到它的时候出队有两种可能——因为比它大的新元素来了而被从队尾弹出或者因为滑出窗口而被从队头弹出。无论是哪种每个元素都只会出队一次。所以循环虽然看起来是嵌套的while加for但所有while操作的总次数是 O(n)整体复杂度就是 O(n)。空间复杂度队列最多同时存k个元素所以是 O(k)。如果把结果数组算进去输出数组本身就是必须的不算额外空间。对比一下暴力法的 O(n × k)这个提升是巨大的。当n 100000, k 50000时暴力法要比较约 25 亿次单调队列只要约 10 万次操作差距肉眼可见。4. 我刷这道题踩过的坑常见问题与排查实录4.1 坑一队列里存值导致窗口过期判断失效这是我见过的初学者最容易犯的错误包括我自己第一次写也没逃过。很多人理解了“维护递减队列”之后直接把值扔进队列里代码长这样dq deque() for i in range(n): while dq and dq[-1] nums[i]: dq.pop() dq.append(nums[i]) if i k and dq[0] nums[i - k]: # 试图用值判断过期 dq.popleft() if i k - 1: result.append(dq[0])这个if i k and dq[0] nums[i - k]看起来很合理但实际一跑就会出错。原因是最开始说的如果窗口出去的那个元素并不是当前队头这个判断根本不会触发它直接就把一个已经该出队的元素留在队列里了。更麻烦的是即使它等于队头的值也可能因为重复元素而误判。所以不要尝试用值去判断过期一定要存下标。4.2 坑二弹出条件用了导致相同元素堆积很多人会纠结nums[dq[-1]] nums[i]这里的等号要不要加。如果你写的是会怎样考虑nums [4, 4, 4, 4]k 2i0队列[0]i1队尾4 4为假因为用的是队列变成[0, 1]结果输出nums[0] 4i2队尾4 4为假队列变成[0, 1, 2]清理队头0 0成立弹出0队列[1, 2]结果输出nums[1] 4i3同理看起来结果没毛病那和的区别到底在哪主要在于队列长度。用时相等元素不会被弹出队列可能会同时保留多个相同最大值的下标队列最长可能超过 k但不会影响正确性只是浪费了一点点空间。用时相同元素会互相顶掉队列更短更高效。两者的结果都一样但推荐用因为队列更精简逻辑也更干净。4.3 坑三窗口过期判断写成了而不是这个更隐蔽。假设k 3当前i 3窗口范围应该是下标[1, 2, 3]。如果队头下标是0它显然已经不在窗口里了。0 3 - 3 0成立所以我们应该用把它弹出去。如果你写成0 0不成立这个已经过期的下标就会留在队列里并且很有可能会被当成最大值输出直接导致答案错误。一句话记法判断过期时用i - k这个边界值已经属于“窗口外”了。4.4 坑四用 Python 的 list 模拟双端队列新手容易图省事直接用list当作队列dq [] ... dq.pop(0) # 弹出队头在 Python 里list.pop(0)是 O(n) 操作因为要移动后面所有元素。如果你在循环里反复pop(0)整体复杂度直接退化到 O(n²)数据规模一上来照样超时。所以务必用collections.deque或者list 头尾双指针手动模拟。这里分享一个面试时能加分的技巧其实你也可以不用 deque而是用一个普通数组配合两个指针来模拟代码看起来更底层展示你对“双端队列本质就是数组加头尾指针”的理解。但日常做题还是deque最方便。4.5 面试官追问为什么不用大顶堆这是一个非常高频的追问。很多人第一反应是“用堆不也能拿到最大值吗”确实大顶堆也可以维护窗口内最大值但有一个麻烦堆不方便删除“滑出窗口的那个特定元素”。标准做法是“延迟删除”——也就是把元素存入堆时连同下标一起存每次取堆顶时不停弹出那些下标已经超出窗口的元素直到堆顶合法。这个写法也能过时间复杂度是 O(n log k)。因为每个元素入堆一次、出堆一次每次都是 O(log k)。而单调队列能做到均摊 O(n)比堆更快而且实现也更简洁。所以面试官更想听到的答案就是在滑动窗口这种“先进先出”的场景下单调队列是更优解。补充一个边界处理如果k 1每个窗口只有一个元素答案就是数组本身单调队列也能正常处理不需要特判。如果k n其实整个数组就一个窗口直接返回全数组最大值即可但单调队列的逻辑也不需要特判因为它会等i n-1时输出唯一的答案。唯一需要特判的是nums为空的情况。5. 举一反三这类题背后的通用套路5.1 什么样的问题适合用单调队列刷题多了你会发现“滑动窗口最大值”只是单调队列的一个典型代表。这个算法的适用场景可以总结为三个关键词滑动窗口、最值、先进先出。比如这一类问题求每个长度为 k 的子数组的最小值把单调递减换成单调递增队头最小就行代码几乎一样。求滑动窗口内的中位数这就不能直接用单调队列了通常需要两个堆或者有序结构但思路仍然是“维护窗口内的数据有序”。求满足某种约束的最长连续子数组比如“绝对差不超过 limit 的最长连续子数组”这题需要同时维护一个最大值单调队列和最小值单调队列然后移动窗口左边界是 239 题的直接升级版。当你拿到一个新题时可以先自我提问三连是否有连续的“窗口”窗口是否只向右滑动是否要实时获取窗口内某种极值信息如果三个答案都是“是”那第一时间想到单调队列准没错。这个思维模式能帮你在面试时候快速定位到正确的解法方向。5.2 相似题对比与联系力扣 239 的兄弟题们很多题表面长得不一样内核其实一模一样。我刷到过几道和 239 高度相关的题给你整理一下方便串联记忆题目核心要求用到的方法与 239 的关系力扣 239 滑动窗口最大值每个窗口的最大值单调递减队列本体剑指 Offer 59-I 滑动窗口的最大值同上同上完全一样力扣 1438 绝对差不超过限制的最长连续子数组维护窗口内最大最小值差两个单调队列239 的升级版力扣 1696 跳跃游戏 VI每个位置可从前面 k 步内转移单调队列优化 DP单调队列用于取前 k 个位置的最大转移值力扣 862 和至少为 K 的最短子数组前缀和 窗口约束单调队列维护索引思想同源但目标不同特别是 1696很多初学者根本想不到它居然也能用单调队列优化。它的本质是dp[i] nums[i] max(dp[i-k..i-1])那max(dp[i-k..i-1])本身就是一个滑动窗口最大值问题。一旦你看穿这层整个题就变得非常清晰。5.3 面试进阶流式输入怎么处理面试官还有一种问法会直接改变题目输入模型如果数组不是一次性全部给到而是一个一个地流式输入你还能用单调队列吗答案是可以而且单调队列天然适合流式处理。你不需要知道整个数组长什么样只需要在每来一个新元素时做那三步操作然后从队头拿答案。对i小于k-1的时候“窗口不够长”你可以先不输出或者输出空值等凑满 k 个再开始产生结果。这种场景对应到工程实践上就是日志系统、实时监控、股票行情里的“最近 k 条数据的最大值”需求。所以刷题并不是纯应试这道题的思路在实际系统中同样有用。理解到这一层你对单调队列的理解就超越“背模板”的水平了。另外我再分享一个调试小技巧如果你发现自己写的程序答案不对先在每次入队、出队操作后打印整个队列里的下标和对应值一步一步对照手算过程找出是哪一步的弹出条件写错了。我当年就是这么定位到自己把写成的。这一招比盯着代码看半天管用得多真的。力扣 239 这道题我第一次刷完只是“看懂了答案”真正理解是后来的事。当时我对着代码在心里跑了七八个用例把队列的每一步变化都写在纸上才彻底想明白“为什么队头一定是最大值”“为什么每个元素只会进出一次”。所以如果你现在还有点懵别急着背代码拿笔在纸上手动模拟一遍模拟完你会发现自己突然就通了。这个习惯也让我在后面刷单调队列优化的 DP 题时少走了很多弯路。