滑动窗口最大值：从暴力到单调队列的O(n)解法详解

最近在刷 LeetCode 热题 100 的时候碰到滑动窗口最大值这道题第一次做还真被恶心到了。题目本身不难理解就是给你一个数组和一个滑动窗口窗口每次往右移动一格让你输出每个窗口里的最大值。但等你真动手写代码用最直白的思路一把梭下去才发现数据稍微给大一点直接超时。这道题在 LeetCode 上是第 239 题也是热题 100 里“滑动窗口”专题的必刷题面试出镜率极高。今天这篇就不绕弯子了直接把这题从暴力到单调队列的完整进化路线捋一遍。尤其会讲清楚单调队列到底在维护什么、为什么双端队列能做到 O(n)、以及写代码时最容易被坑的几个边界条件。适合刚刷完链表和二叉树、准备进入“滑动窗口”专题的选手也适合每次看题解都懂、自己写就废的兄弟姐妹。我尽量把每一步的“为什么”也讲透而不是扔给你一段代码让你背。1. 先从暴力解法说起看看问题到底出在哪1.1 最直观的思路每个窗口重新扫一遍先说一下最符合直觉的解法从左到右滑动窗口每到一个新窗口就遍历窗口里这 k 个元素找出最大值存进结果数组。假设 nums 长度为 n窗口大小为 k那么一共有 n - k 1 个窗口。每个窗口里都扫 k 次总时间复杂度就是 O(n × k)。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; }代码写起来确实是五分钟的事干净、直观、不会错。但你把示例数据换成 LeetCode 给的测试范围看一眼n 最大能到 10 万k 最大也能到 10 万这时候 O(n × k) 最坏就是 100 亿次操作不超时才怪。所以暴力解法唯一的作用就是帮你验证题意理解对了没真要提交等着你的就是一个大大的 Time Limit Exceeded。1.2 暴力的根本问题每次都在重复干活如果只是“超时”两个字那这题还不算难。难点在于你得想清楚一个问题窗口每次只移动一格也就是说新窗口和旧窗口相比只丢掉了最左边一个元素、新增了最右边一个元素中间那 k-1 个元素根本没变。那我们为什么要把它们重新扫一遍理想的做法是上一个窗口的最大值还能不能继续用如果能怎么用如果不能怎么快速找到新的最大值这就引出了这题最核心的思考方向——信息复用。既然窗口的变化是局部的我们应该设计一个数据结构随着窗口的滑动动态地维护“当前窗口内候选最大值”的顺序而不是每次从头开始算。提示暴力解法就像你每次去教室找一个人明明知道他上次坐的位置下次偏要满教室重新找一遍。而我们想要的是记住一小撮“有可能成为最大值的人”每次有新人进来先跟这一小撮比一比这样找起来就快多了。2. 单调队列这道题真正的主角2.1 为什么是双端队列而且队列里要维护成递减先说结论我们维护一个双端队列 deque队列里存的是数组元素的下标并且保证下标对应的元素值在队列里是严格递减的。也就是说队头永远是当前队列里的最大值。为什么用双端队列而不是普通队列因为滑动窗口移动的时候有两类元素需要清理窗口滑过了某些元素的下标已经不在窗口范围里了这类元素必须从队头移除普通队列也能干这个。新元素入队时如果它比队尾元素大那队尾那些“老元素”永远不可能再成为最大值了必须从队尾弹出去。普通队列只能一头进一头出做不到队尾也能弹出所以必须用双端队列。为什么队列里的值要单调递减而不是递增你想我们要的是窗口最大值队头直接给答案就行了。如果队列里从头到尾是递减的队头就是最大的。反过来如果是递增那你还得翻到队尾才能拿到最大值那这个队列就没有意义了。2.2 三个关键问题存值还是存下标什么时候弹出什么时候记录答案这道题我最开始写的时候习惯性在队列里存元素的值结果左边界判断死活写不对。后来才想明白队列里必须存下标不能存值。原因很简单我们需要判断队头元素是不是已经滑出窗口了只有拿到下标才能判断。存值的话你还得再去数组里找一遍这个值出现在哪遇到重复值就完全懵了。判断队头过期的条件如果 deque 的队头下标 i - k说明窗口已经滑过了这个元素把它从队头弹出。这里的 i 是当前正在遍历的数组下标。维护单调性的入队逻辑当新元素 nums[i] 准备入队时从队尾开始把所有值小于等于 nums[i] 的下标全部弹出。注意这里是“小于等于”而不是“小于”这是很多题解不强调但实际很重要的一个点。为什么等于也要弹掉因为同样的值新元素的下标更大存活时间更久所以在窗口里的生命周期更长旧下标完全可以被新下标替代。那什么时候记录答案呢两个时机都可以先让窗口完整形成i k-1之后再右移一格记录一次答案或者边遍历边判断只要 i k-1就说明窗口已经成形直接取队头元素作为答案。两种写法最后代码不一样但本质没区别后面会详细对比。3. 手工模拟一遍看完这个你绝对能懂3.1 用一个具体数组走完全程光讲理论容易被绕晕我拿 LeetCode 官方的示例数组走一遍nums [1,3,-1,-3,5,3,6,7]k 3。目标是输出每个窗口的最大值。先初始化一个空的双端队列 deque然后从 i 0 开始遍历当前 i元素值队列变化左侧为队头窗口范围当前窗口最大值01队列为空直接入队[0]还没满-13队尾 1 3弹出下标 0入队下标 1[1]还没满-2-1队尾元素 3 -1直接入队[1, 2][0,2]nums[1]33-3队尾 -1 -3直接入队[1, 2, 3][1,3]队头下标1在窗口内nums[1]345队尾 -3 5 弹出-1 5 弹出3 5 弹出入队下标4[4][2,4]nums[4]553队尾 5 3直接入队[4, 5][3,5]nums[4]566队尾 3 6 弹出5 6 弹出入队下标6[6][4,6]nums[6]677队尾 6 7 弹出入队下标7[7][5,7]nums[7]7最终输出[3, 3, 5, 5, 6, 7]和 LeetCode 官方输出完全一致。3.2 这个模拟过程里藏着的三个关键转折第一次写代码的人最容易卡在 i 1 这一步。这时候队列里已经有了下标 0也就是元素 1结果新元素 3 一进来直接把 1 弹掉了。你可能会问万一之后的窗口里1 比 3 活得久呢答案是不会。因为新元素 3 的下标比 1 大说明 3 比 1 更晚过期。而且 3 的值比 1 大。所以无论从哪个角度看只要有 3 在窗口里1 就永远不可能是窗口的最大值。1 的“利用价值”已经没了留着它纯属浪费空间。这也是单调队列名字里“单调”二字的真正含义——队列里的值单调递减新来的大的会把前面所有小的全部挤掉。第二个关键点是 i 4元素 5 入队时不仅把 -3、-1 弹掉了还顺便把队头最大的 3 也弹掉了。这里注意3 是当前队头并没有过期下标 1 还在窗口范围 [2,4] 内。但 5 比 3 大而且 5 的下标比 3 大所以 3 从此刻起就永久出局了。这就是单调队列比“优先队列”好在哪的地方——优先队列只能看到最大值想删除某个非最大元素麻烦得很但单调队列可以通过队尾弹出把“已经不可能成为最大值”的元素提前清理掉保证每个元素最多入队一次、出队一次。第三个关键点是 i 5元素 3 入队时队头还是 5新元素 3 并没有把 5 弹掉而是老老实实排在队尾。存在队列里的 [4, 5] 是啥意思意思就是 5 是目前最大的3 是第二大的候选者。万一窗口往右滑5 先过期了那 3 就有机会顶上。这就是为什么我们需要维护一整条“候选链”而不是只留一个最大值。如果只留一个最大值它一过期你就抓瞎了得重新扫描整个窗口。4. 代码实现照着写不会错但这几个细节要注意4.1 标准 Java 解法public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; // deque 里存的是下标 ArrayDequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 清理过期元素队头 if (!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[i - k 1] nums[deque.peekFirst()]; } } return ans; }这里有一个非常容易被忽略的细节清理过期元素用的是而不是。为什么当 i k 时新的窗口范围是 [1, k]此时 i - k 0也就是说下标 0 已经被滑出窗口了。如果队头刚好是下标 0就必须弹出来。用能保证所有下标小于等于 i - k 的都算过期。如果你写成下标正好等于 i - k 的元素就永远不会被清理错误只会在特定测试用例下出现非常隐蔽。还有一个隐藏问题第 2 步和第 1 步的顺序能换吗我见过很多题解是先维护单调性、再清理过期元素实测也能过。但你细想一下有个边界情况假如 i 足够大新元素入队时队尾那些过期但还没被弹出的元素会不会干扰单调性我举个例子nums [4, 3, 2, 1]k 2。当 i 2 时窗口范围是 [1,2]下标 0 已经过期了。如果先做单调性维护此时 deque 是 [0, 1]元素 4、3nums[2] 2从队尾开始比较队尾是下标 1元素 33 2所以不会弹出任何东西2 直接入队。然后第 1 步清理过期元素把队头下标 0 弹出去此时队列变成 [1, 2]结果正确。但换个数据nums [4, 1, 3, 2]k 2i 2 时deque 是 [0, 1]nums[2] 3。如果先维护单调性从队尾看下标 1 的元素 1 3弹出再看队尾下标 0 的元素 4 3停止。此时队列变成 [0]然后 3 入队[0, 2]。接着第 1 步清理过期i - k 0弹出队头下标 0队列变成 [2]结果正确。那如果先清理过期元素呢i 2 时先看队头i - k 0队头是 0等于 0弹出。队列变成 [1]元素 1然后维护单调性1 3弹出3 入队。结果和上面一样正确。两个顺序在绝大多数情况下都对。但我个人习惯先清理过期元素理由很简单过期元素本来就不该留在队列里参与任何比较提前清理可以让你在调试的时候心里更踏实队列里的元素始终都是“合法窗口范围内的候选值”。当然如果你先维护单调性再清理代码也能过LeetCode 的测试用例不会纠结这个但工程上还是推荐“先清过期再维护单调性”这个顺序。4.2 另一种常见写法先把第一个窗口填满再滑动上面的写法是“边遍历边判断窗口是否成形”还有很多人喜欢另一种写法先把前 k 个元素一次性处理完然后从 k 开始一次循环每次右移一格并收集答案。贴出来对比一下public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; int index 0; ArrayDequeInteger deque new ArrayDeque(); // 先处理第一个窗口 for (int i 0; i k; i) { while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); } ans[index] nums[deque.peekFirst()]; // 再处理后续窗口 for (int i k; i n; i) { if (!deque.isEmpty() deque.peekFirst() i - k) { deque.pollFirst(); } while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); ans[index] nums[deque.peekFirst()]; } return ans; }两种写法我个人推荐第一种。为什么因为第一种写法把四个步骤统一在一个循环里思路更连贯少了一截“先处理第一个窗口”的特殊代码。不过第二种写法的好处是你对“当前窗口已成形”这件事理解得更直观适合初学者把窗口概念在代码里具象化。二选一就行别两种混着写不然容易把自己绕晕。4.3 C 和 Python 的版本差异提醒C 版本用std::deque就行下标用int完全够。要注意的点是 C 的deque::back()和deque::pop_back()组合操作以及队头用front()和pop_front()。写法上跟 Java 一模一样只是 API 名字换了。class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint ans; dequeint q; for (int i 0; i nums.size(); i) { if (!q.empty() q.front() i - k) { q.pop_front(); } while (!q.empty() nums[q.back()] nums[i]) { q.pop_back(); } q.push_back(i); if (i k - 1) { ans.push_back(nums[q.front()]); } } return ans; } };Python 的话标准库collections.deque一样。Python 写这道题有一个很常见的坑如果你用列表模拟队列pop(0)是 O(n) 操作整体复杂度就变成了 O(n × k)又回到暴力了。所以要么用collections.deque要么用数组配合头尾两个指针自己模拟千万不要图省事用list.pop(0)。from collections import deque def maxSlidingWindow(nums, k): q deque() ans [] for i, num in enumerate(nums): if q and q[0] i - k: q.popleft() while q and nums[q[-1]] num: q.pop() q.append(i) if i k - 1: ans.append(nums[q[0]]) return ans5. 复杂度分析与常见问题排查5.1 为什么时间复杂度是 O(n) 而不是 O(n × k)这是面试被追问最多的问题也是最需要想清楚的问题。外层循环确实遍历了 n 个元素但内层 while 循环不是每次都会执行 k 次。关键点在于每个元素最多被加入队列一次最多被弹出队列一次。弹出操作分两种一种是新元素来了把队尾所有比它小的都弹掉另一种是窗口过期把队头出局的元素弹掉。无论哪种每次弹出一个元素就意味着这个元素之后再也不会进队列了。所以整个算法执行过程中所有入队操作加起来最多 n 次所有出队操作加起来最多 n 次均摊到每个循环里就是常数级操作。总时间复杂度就是 O(n)。空间复杂度是 O(k)因为队列里最多同时存 k 个元素这是窗口大小限制的。说明如果你面试被问到“这个内层 while 会不会导致最坏情况变成 O(n × k)”你就用上面这个“每个元素只入队一次、只出队一次”的论证方式回答。这是一个均摊分析的经典例子比背答案可靠得多。5.2 常见坑一队列里存值不存下标这个坑我踩过。刚开始写的时候为了看起来直观我在队列里直接存元素值然后判断过期的时候发现根本没有办法判断队头是不是已经滑出窗口了。有人会说那我在队列里存一个二元组 (value, index) 总行了吧也行但没必要一个下标的 int 数组就够了取值去原数组里拿就行。存下标还有一个好处重复元素也不怕因为每个下标是唯一的。5.3 常见坑二Java 里用了 LinkedList 而不是 ArrayDequeLeetCode 官方题解用的是ArrayDeque但很多人图省事用LinkedList其实也能过。不过从性能角度说ArrayDeque底层是循环数组LinkedList底层是链表随机访问和缓存友好性上ArrayDeque更优。刷题的时候没必要在意这个级别的性能差异但如果你去面试手写最好用ArrayDeque因为面试官大概率会顺口问一句“为什么不用 LinkedList”你要能说出数组比链表更省内存、缓存更友好这几个点。另外一个 Java 相关的坑ArrayDeque不允许添加 null 元素。这个题里我们存的是下标不会为 null所以没问题。但如果你改一下题目要存的东西就要注意了。5.4 常见坑三边界下标的“差一错误”收集答案的时候ans[i - k 1] nums[deque.peekFirst()]这一步最容易写错。我一开始写的是ans[i]结果数组下标越界或错位。理清楚逻辑其实不难当 i k - 1 时第一个窗口刚刚成形这个窗口的起点是 0所以答案应该存在ans[0]。此时i - k 1 0对上了。后面 i 每增加 1窗口起点也增加 1始终满足ans[i - k 1]这个规律。5.5 常见坑四permutation 测试数据下的重复元素处理题目数据范围里可能有大量重复元素。比如 nums [5, 5, 5, 5]k 2。如果你的单调性维护用的是而不是会出现什么结果第一个 5 进队列第二个 5 入队时队尾元素是 55 5 为 false所以第二个 5 不会弹出队尾的第一个 5队列变成 [0, 1]看起来也没错因为当前窗口最大值还是 5。但你再往后走窗口继续滑动队头下标 0 过期弹出队头变成下标 1然后第三个 5 入队。如果一直用队列会攒出一堆值相同的旧下标浪费空间倒是小事最致命的是队头一直是那个最早入队的 5一旦它过期队列里还剩下一堆同样值的下标可以顶上来虽然结果不会错但队列长度可能在某些极端情况下拖成 O(k)甚至在更复杂的题目里导致错误。所以统一用把旧值弹掉让新值替换旧值是最稳妥的选择。5.6 常见问题速查表症状原因解决方案提交超时暴力解法每个窗口重新遍历 k 个元素改用单调队列或优先队列优化答案错误只在部分用例出现队头过期判断用了而不是判断条件换成 i - k答案错位结果长度正确但内容不对收集答案时下标写错记住ans[i - k 1] nums[deque.peekFirst()]队列里有元素但取队头报错没有判空直接在空队列上取 peekFirst所有队列操作前先判空Python 超时用 list 的 pop(0) 模拟队列改用 collections.deque6. 延伸这套思路还能秒杀哪些题滑动窗口最大值不是一道孤立的题它是“单调队列”这个数据结构最经典的入门模板。吃透它之后下面这几类问题你都应该能快速反应过来。第一类是同模板的替换题。比如剑指 Offer 59 - I 滑动窗口的最大值几乎就是 LeetCode 239 的换皮代码可以直接复用。还有 LeetCode 2398预算内的最多机器人数目也是滑动窗口只是判定条件多了一个“花费总和”核心还是维护窗口里的最大值。第二类是“滑动窗口最小值”类问题。思路一模一样只是把单调递减变成单调递增队头就是窗口最小值。比如求滑动窗口最小值、或者求“窗口内最大最小差值”这类型的问题一般就是维护一个递减队列和一个递增队列两头都顾上。第三类是更进阶的前缀和 单调队列。LeetCode 862和至少为 K 的最短子数组就是这类经典题。它需要先计算前缀和然后用单调队列维护前缀和的下标队列里保持前缀和递增这样窗口左边界就能快速移动。这类题比本题难不少但核心思想还是“单调队列维护候选值”只是候选值从窗口元素变成了前缀和。你如果能把 239 的单调性理解透做 862 的时候至少能看懂题解在干嘛不至于完全懵。还有一类是滑动窗口 数据结构的综合题比如 LeetCode 480滑动窗口中位数以及经典的“每个窗口的最大最小值之差”类问题。这些不能只靠单调队列解决中位数需要两个堆或者有序结构但分析框架还是那套——每次窗口移动怎么快速增删元素并维护你关心的统计量。先掌握了单调队列再看这些题才谈得上有降维打击的可能。注意滑动窗口类题目的通用套路是“右边界扩张 左边界收缩 窗口内数据结构的维护”。不同题目的难点都集中在第三步有时候需要哈希表维护频次如最小覆盖子串有时候需要单调队列维护极值如本题有时候需要堆维护中位数如 480。你先判断窗口里要维护什么信息再选对应的数据结构思路会清晰很多。写到这里这题的核心已经讲透了。我个人刷这道题的体验是第一遍写暴力超时第二遍看题解觉得“就这就这”第三遍自己合上书手写卡在过期判断和单调性维护的顺序上第四遍才彻底捋顺。所以如果你现在还没完全懂别急拿纸笔把上面那个表格手工模拟一遍模拟完了再自己敲代码比看十遍题解都管用。这题值得反复刷因为它不光是一道面试题更是你理解单调队列、理解均摊分析、理解滑动窗口类问题的基石。