企业官网建设流程全解析

最近在刷 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，队列里存的是数组元素的下标，并且保证下标对应的元素值在队列里是严格递减的。也就是说，队头永远是当前队列里的最大值。

为什么用双端队列而不是普通队列？因为滑动窗口移动的时候，有两类元素需要清理：

1. 窗口滑过了，某些元素的下标已经不在窗口范围里了，这类元素必须从队头移除，普通队列也能干这个。
2. 新元素入队时，如果它比队尾元素大，那队尾那些“老元素”永远不可能再成为最大值了，必须从队尾弹出去。普通队列只能一头进一头出，做不到队尾也能弹出，所以必须用双端队列。

为什么队列里的值要单调递减而不是递增？你想，我们要的是窗口最大值，队头直接给答案就行了。如果队列里从头到尾是递减的，队头就是最大的。反过来如果是递增，那你还得翻到队尾才能拿到最大值，那这个队列就没有意义了。

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 开始遍历：

最终输出：[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 里存的是下标 ArrayDeque<Integer> 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、3），nums[2] = 2，从队尾开始比较，队尾是下标 1，元素 3，3 > 2，所以不会弹出任何东西，2 直接入队。然后第 1 步清理过期元素，把队头下标 0 弹出去，此时队列变成 [1, 2]，结果正确。

但换个数据，nums = [4, 1, 3, 2]，k = 2，i = 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; ArrayDeque<Integer> 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: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> ans; deque<int> 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 ans

5. 复杂度分析与常见问题排查

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 而不是 ArrayDeque

LeetCode 官方题解用的是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 入队时，队尾元素是 5，5 < 5 为 false，所以第二个 5 不会弹出队尾的第一个 5，队列变成 [0, 1]，看起来也没错，因为当前窗口最大值还是 5。

但你再往后走，窗口继续滑动，队头下标 0 过期弹出，队头变成下标 1，然后第三个 5 入队。如果一直用<，队列会攒出一堆值相同的旧下标，浪费空间倒是小事，最致命的是队头一直是那个最早入队的 5，一旦它过期，队列里还剩下一堆同样值的下标可以顶上来，虽然结果不会错，但队列长度可能在某些极端情况下拖成 O(k)，甚至在更复杂的题目里导致错误。所以统一用<=把旧值弹掉，让新值替换旧值，是最稳妥的选择。

5.6 常见问题速查表

6. 延伸：这套思路还能秒杀哪些题？

滑动窗口最大值不是一道孤立的题，它是“单调队列”这个数据结构最经典的入门模板。吃透它之后，下面这几类问题你都应该能快速反应过来。

第一类是同模板的替换题。比如剑指 Offer 59 - I 滑动窗口的最大值，几乎就是 LeetCode 239 的换皮，代码可以直接复用。还有 LeetCode 2398（预算内的最多机器人数目），也是滑动窗口，只是判定条件多了一个“花费总和”，核心还是维护窗口里的最大值。

第二类是“滑动窗口最小值”类问题。思路一模一样，只是把单调递减变成单调递增，队头就是窗口最小值。比如求滑动窗口最小值、或者求“窗口内最大最小差值”这类型的问题，一般就是维护一个递减队列和一个递增队列，两头都顾上。

第三类是更进阶的前缀和 + 单调队列。LeetCode 862（和至少为 K 的最短子数组）就是这类经典题。它需要先计算前缀和，然后用单调队列维护前缀和的下标，队列里保持前缀和递增，这样窗口左边界就能快速移动。这类题比本题难不少，但核心思想还是“单调队列维护候选值”，只是候选值从窗口元素变成了前缀和。你如果能把 239 的单调性理解透，做 862 的时候至少能看懂题解在干嘛，不至于完全懵。

还有一类是滑动窗口 + 数据结构的综合题，比如 LeetCode 480（滑动窗口中位数），以及经典的“每个窗口的最大最小值之差”类问题。这些不能只靠单调队列解决，中位数需要两个堆或者有序结构，但分析框架还是那套——每次窗口移动，怎么快速增删元素并维护你关心的统计量。先掌握了单调队列，再看这些题才谈得上有降维打击的可能。

注意：滑动窗口类题目的通用套路是“右边界扩张 + 左边界收缩 + 窗口内数据结构的维护”。不同题目的难点都集中在第三步：有时候需要哈希表维护频次（如最小覆盖子串），有时候需要单调队列维护极值（如本题），有时候需要堆维护中位数（如 480）。你先判断窗口里要维护什么信息，再选对应的数据结构，思路会清晰很多。

写到这里，这题的核心已经讲透了。我个人刷这道题的体验是：第一遍写暴力，超时；第二遍看题解，觉得“就这就这”；第三遍自己合上书手写，卡在过期判断和单调性维护的顺序上；第四遍才彻底捋顺。所以如果你现在还没完全懂，别急，拿纸笔把上面那个表格手工模拟一遍，模拟完了再自己敲代码，比看十遍题解都管用。这题值得反复刷，因为它不光是一道面试题，更是你理解单调队列、理解均摊分析、理解滑动窗口类问题的基石。