滑动窗口最大值优化：单调队列如何把O(nk)降到O(n)

我刷LeetCode热题100的时候滑动窗口最大值这道题卡了我一阵子。不是写不出暴力解法而是每次提交都卡在超时上后来把单调队列的思路彻底理清才发现这道题考察的根本不是“你会不会用队列”而是“你愿不愿意多花几分钟去搞懂数据结构为什么这样选”。这篇我就从暴力解法开始把滑动窗口最大值从 O(nk) 优化到 O(n) 的完整推理过程、代码细节和踩坑经验都摊开讲清楚。无论你是刚开始刷题的新手还是想重新巩固单调队列思路的老手这篇应该都能给你一点参考。1. 暴力解先算算账为什么O(nk)连测试都过不了1.1 题目到底在问什么LeetCode 239 滑动窗口最大值描述非常简洁给定一个整数数组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,5,3]最大值是5第五个窗口[5,3,6]最大值是6第六个窗口[3,6,7]最大值是7最终返回[3,3,5,5,6,7]。数组长度为n窗口会滑动n-k1次所以答案数组的长度也是n-k1。很多第一次接触这题的人包括我第一反应都是这不是送分题吗每次把窗口里的数扫一遍找最大然后整体右移一格不就行了1.2 暴力代码和它的复杂度如果你用暴力思路写代码大概是这样的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 Integer.MIN_VALUE; for (int j i; j i k; j) { max Math.max(max, nums[j]); } ans[i] max; } return ans; } }逻辑没有任何问题但它的时间复杂度是 O(nk)。外层循环有n-k1个窗口内层每个窗口要遍历k个元素总操作次数大约是(n-k1) * k。LeetCode 上这题的数组长度能达到10^5级别k也能到10^5级别那么最坏情况下就是10^10次操作。这个量级在 OJ 上跑超时是必然的根本不用怀疑。1.3 真正浪费的计算在哪里暴力解慢是因为窗口每次只向右移动一格但中间k-1个元素其实在上一个窗口里已经被完整扫过一遍了。也就是说数组里靠中间的那些元素每个都被重复读取了大约k次。窗口真正变化的只有两端最左边移出一个元素最右边新增一个元素。如果我们能把上一个窗口的“最大值信息”保留下来只处理两端的变化就不需要每次从头扫描。这个观察很重要。所有滑动窗口优化方案的出发点都是同一个想法如何让信息在窗口之间“接力”而不是“重算”。2. 单调队列的维护规则从队尾淘汰“废物”从队首清理“过期”2.1 为什么普通队列和栈都做不到要解决这个问题我们需要一个数据结构同时支持四个操作从队尾加入新元素从队尾淘汰旧元素因为旧元素可能永远不再需要了从队首获取当前最大值从队首淘汰已经滑出窗口的过期元素。普通队列只支持队尾进、队首出想从队尾淘汰元素是不可能的。栈虽然能从尾部弹出但最大的问题在于如果你用栈存窗口元素最大值可能已经压在栈底了根本取不出来。所以这两者都不满足需求。双端队列deque是唯一能自然满足这四种操作的线性结构。这也是为什么这道题的正确解法几乎必然要落到双端队列头上。2.2 单调递减队列的维护逻辑用单调队列解这道题核心是维护一个从队首到队尾“下标递增、对应值递减”的队列。也就是说队首永远是当前窗口里最大值的下标。每处理一个新元素nums[i]分四步走队尾淘汰只要队尾下标对应的值 nums[i]就把队尾弹出。因为这些旧值已经不可能再成为当前或未来窗口的最大值了。当前下标入队把i从队尾入队。注意队列里存的是下标不是值本身。队首过期淘汰如果队首下标已经不在当前窗口范围内小于i - k 1就把队首弹出。收集答案当窗口已经成形i k-1时队首下标对应的值就是当前窗口最大值。这里很多人第一次看会懵为什么队尾淘汰用而不是我最初也不太明白后来才想清楚。当新元素和队尾元素相等时新元素的下标更大意味着它在窗口里存活的时间更久。既然两者值一样旧的那个就永远不可能再成为最大值了留着纯粹是占地方。所以用把旧的等值元素淘汰掉队列更紧凑后续也更高效。用也能得出正确答案但队列中会残留几个冗余节点让队列长度比实际需要的更长。2.3 为什么均摊复杂度是 O(n)单调队列让人困惑的地方在于代码里明明有个while循环为什么总复杂度还是 O(n)关键在于每个下标在整个过程中最多入队一次、出队一次。一个元素从队尾入队后要么因为被更大的新元素从队尾淘汰要么因为滑出窗口从队首过期总之只会被处理一次。所以虽然while看起来像嵌套循环但所有内层操作的总次数加起来就是 O(n)均摊到每个元素上就是 O(1)。这是“均摊复杂度”里比较典型的一个例子也是单调队列在算法面试中备受偏爱的原因代码短思路巧妙复杂度分析还很有讲究。2.4 一个更好记的类比把单调队列想象成一个窗口内的“选秀现场”。新选手进来如果比队尾选手强队尾选手直接走人因为新选手在窗口里待的时间更长旧选手再也轮不到上场。如果新选手不够强那就站到队尾排队等着前面的人要么被更强的淘汰要么超时离场。队伍最前面的永远是当前最强的那个选手。窗口每次右移就相当于有人站到了舞台范围之外自动离场。这么一想维护逻辑就顺了新人强顶掉队尾时间到清掉队首。3. 三种语言的实际代码细节都在注释里3.1 Java用 ArrayDeque 就够了Java 刷题时直接用ArrayDeque实现双端队列它基于循环数组实现内存连续、访问快比LinkedList更合适LinkedList 的链表节点开销大性能在频繁增删时也不占优势。class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; if (n 0 || k 0) { return new int[0]; } int[] ans new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 队尾淘汰队尾值不大于当前值时直接弹掉 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 2. 当前下标入队 deque.offerLast(i); // 3. 队首过期当前窗口左边界是 i - k 1 if (deque.peekFirst() i - k 1) { deque.pollFirst(); } // 4. 窗口成形后开始收集答案 if (i k - 1) { ans[i - k 1] nums[deque.peekFirst()]; } } return ans; } }注意第 3 步我写的是 i - k 1写成 i - k也完全等价但前者更容易理解队首下标如果比窗口左边界还小就是过期了。3.2 Cdeque 的标准操作C 标准库的deque使用起来更直白和 Java 在 API 上略有差异但核心逻辑一模一样class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); vectorint ans; 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 1) { dq.pop_front(); } if (i k - 1) { ans.push_back(nums[dq.front()]); } } return ans; } };3.3 Pythoncollections.dequePython 刷题用collections.deque语法上最简洁但要注意不能用下标访问队首以外的地方虽然 deque 支持[0]取队首但不支持随机访问中间元素这里我们也不需要from collections import deque from typing import List class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: dq deque() ans [] for i, x in enumerate(nums): while dq and nums[dq[-1]] x: dq.pop() dq.append(i) if dq[0] i - k 1: dq.popleft() if i k - 1: ans.append(nums[dq[0]]) return ans3.4 三种语言的 API 对照操作Java ArrayDequeC dequePython collections.deque队首取元素peekFirst()front()dq[0]队首弹出pollFirst()pop_front()popleft()队尾取元素peekLast()back()dq[-1]队尾弹出pollLast()pop_back()pop()队尾入队offerLast(i)push_back(i)append(i)平时只用一种语言刷题的话记住一种就行但最好理解其他语言版本因为面试时你说不定会被要求换语言写思路。4. 我调试时反复踩的几个坑索引、等号、过期判断4.1 坑一下意识把值存进队列我第一次写的时候队列里存的是值不是下标写一半发现完全没法做“过期判断”。窗口滑动时我怎么知道队首这个值是不是已经滑出窗口了如果只存值两个相同值的元素连区分都做不到。所以记住队列里存的一定是下标比较大小的时候再用下标去数组里取值。存下标才是这个解法的灵魂它让你的队列元素有了“身份”能用来判断窗口位置。4.2 坑二窗口左边界计算错一个下标窗口右端是i左端是i - k 1。很多人会写成i - k导致边界判断出错。举个例子i 2k 3窗口应该是下标[0, 1, 2]左边界是0。i - k 1 0正确i - k -1看起来差了一个数。虽然过期判断用 i - k和 i - k 1是等价的但如果你搞混了“何时该用、何时该用”边界就会差出 1 个下标直接导致答案错误。我的习惯是先明确窗口左边界left i - k 1然后统一用“队首下标 left时过期”。这样不容易错。4.3 坑三答案数组的收集时机答案数组长度为n - k 1但收集答案不能从i 0就开始因为窗口还没成形。必须等到i k - 1也就是窗口里的元素已经凑满k个之后才能开始记录。有些解法喜欢先把前k个元素预处理进队列再循环处理后面的元素这也行但预处理阶段容易漏掉第一个窗口的答案收集或者多处理一次k-1这个下标。相比之下我是觉得统一在一个循环里处理、用if (i k - 1)控制收集时机最不容易出错。4.4 边界情况空数组、k1、kn边界测试很容易挂列出来给你参考nums为空直接返回空数组k 1每个元素单独成窗口答案就是数组本身算法也应该正确处理k n只有一个窗口答案只有一个数数组全部相同比如[7,7,7,7]k 2因为用了淘汰旧等值队列里永远只保留最新那个 7最终答案全是 7正确数组升序[1,2,3,4,5]每个新元素进来都会把队尾全部弹出队列长度始终为 1这是单调递增数据下的最理想情况数组降序[5,4,3,2,1]每个元素都能入队队首一直是 5直到 5 过期前队列长度会逐渐接近窗口大小这也是正常现象不要以为队列长度一定小于 k。5. 优先队列大根堆也能做写起来更直观但性能差在哪5.1 大根堆方案的思路如果你在面试时一时想不起单调队列也可以先给面试官一个更直观的方案用大根堆维护窗口内所有元素。每次遍历到一个新元素就把(nums[i], i)放进堆里。堆顶永远是当前堆里值最大的元素但要判断这个堆顶元素的下标是否还在当前窗口内。如果已经过期就弹出堆顶继续看下一个堆顶直到堆顶有效。class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; PriorityQueueint[] pq new PriorityQueue( (a, b) - b[0] - a[0] ); for (int i 0; i n; i) { pq.offer(new int[]{nums[i], i}); while (pq.peek()[1] i - k 1) { pq.poll(); } if (i k - 1) { ans[i - k 1] pq.peek()[0]; } } return ans; } }注意这里PriorityQueueint[]的比较器如果写成b[0] - a[0]在极端值溢出的情况下会有风险更严谨的写法是Comparator.comparingInt((int[] a) - a[0]).reversed()。刷题时直接用差值大多数情况下没影响但心里要知道这个隐患。5.2 时间和空间的真实差距方案时间复杂度空间复杂度每个元素均摊暴力扫描O(nk)O(1)多次访问大根堆O(n log k)O(k)O(log k) 堆调整单调队列O(n)O(k)O(1)实际跑 LeetCode 的大数据用例时堆和单调队列的差距是能感受到的n 10^5时大约差一个数量级。堆还有一个隐蔽问题过期元素是“懒删除”的只有当它们堆顶挡住答案时才被弹出所以堆里会暂时积压一些已经过期的元素。在流式数据持续输入的场景下如果不做定期清理堆的内存占用会持续增长。单调队列没有这个问题因为过期元素每次都会被及时弹出。5.3 什么情况下堆反而更合适但别把单调队列吹上天。如果k很小比如 3、4堆和单调队列的时间差距几乎可以忽略堆反而更好写、更好解释。如果题目要求的不是最大值而是窗口内的第k大值或者中位数比如 LeetCode 480 滑动窗口中位数单调队列就不适用了得改用两个堆来维护对顶结构。选数据结构的本质是匹配需求没有银弹。6. 同一套思路还能用来扫掉哪些题6.1 固定窗口题型的通用模板滑动窗口最大值这类题可以用一个模板去套left 0 for right in range(n): # 把 nums[right] 加入窗口对应的数据结构 # 必要时做数据结构的内部淘汰/清理 while 窗口不满足条件: # 移动 left并从数据结构中移除 nums[left] pass if right - left 1 k: # 窗口成形收集答案 pass关键不在于模板本身而在于你想清楚“窗口内的信息应该用什么结构维护”。6.2 滑动窗口最小值就是改一个符号如果把题目改成“滑动窗口最小值”单调队列的逻辑完全不变只需要把队列从“单调递减”改成“单调递增”队尾淘汰条件从改成队首就是当前窗口最小值。学一道题等于会两道题这是这道题性价比最高的地方。6.3 相关题目列表LeetCode 3 无重复字符的最长子串可变窗口 哈希集合LeetCode 76 最小覆盖子串可变窗口 计数LeetCode 209 长度最小的子数组双指针窗口LeetCode 480 滑动窗口中位数双堆 / 延迟删除它们的共同点是窗口本身只是遍历数组的方式难点全在“窗口内信息用什么数据结构维护、怎么高效更新”。6.4 实际工程里的影子滑动窗口最大值这类算法不是只活在 OJ 里。工程上做传感器降噪会用滑动窗口滤波器移动平均滤波的本质就是在固定窗口里反复求和中值滤波则是在窗口内找中位数——和“滑动窗口最大值/最小值”几乎是同一类问题。在实时流式计算里如果要求每条数据到达后都能以 O(1) 均摊成本拿到当前窗口的极值单调队列比排序和堆都更适合。最后分享一个我自己形成的小习惯遇到滑动窗口维护极值的题先问自己三个问题——窗口大小是否固定数据结构能不能支持两端操作过期元素能不能高效剔除三个问题顺着答下来选型基本不会跑偏。希望这篇能帮你把 LeetCode 热题100 里这道经典题彻底吃透下次再遇到同类问题直接秒。