企业官网建设流程全解析

刷算法题的人应该都有这种体会：有些题第一次看答案觉得“也不难嘛”，真让自己写却总是卡在某个边界条件上。力扣239滑动窗口最大值就是典型，它考的不只是“会遍历数组”，还考察你能否在窗口滑动的动态过程中，用一个合适的数据结构持续拿到最大值。Java解法里最经典也最常用的是双端队列，维护一条“单调队列”，把时间复杂度压到O(n)。这篇文章写给正在刷题、准备面试的同学，也写给想把双端队列用法彻底吃透的人，我会从暴力解法为什么超时讲起，一直讲到可运行的Java代码、边界测试和面试追问中间的坑，保证你看完能直接照着写。

1. 先看题面：为什么暴力解会被判超时

1.1 题面到底在问什么

题目给定一个整数数组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]。

这里有一点非常容易被忽略：窗口是“先进先出”的结构，每次都从右边进一个新元素，从左边走一个旧元素。但最大值本身不像队列头那样固定，它可能在新元素进来时被替换，也可能在旧元素被移走时跟着消失。正因为“最大值的生命周期”和“窗口的滑动节奏”不是一一对应的，这题才需要专门设计算法。

1.2 暴力解法的时间账

最直观的想法是：每次窗口滑动，直接遍历窗口里的k个元素，找出最大值。

public int[] maxSlidingWindowViolent(int[] nums, int k) { int n = nums.length; int[] res = 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]); } res[i] = max; } return res; }

逻辑没错，但复杂度是O(n*k)。假设n = 10^5，k = 5 * 10^4，那约等于5 * 10^9次比较，Java 跑起来基本直接超时。

更麻烦的是，即便k比较小，比如k = 10、n = 10^6，那也是10^7级别，勉强能跑，可一旦数据量上涨就兜不住。力扣给这道题的定位就是要求在线性时间内解决问题，暴力思路只能用来验证小数据样本，不能作为最终提交方案。

1.3 为什么“记住当前最大值”也不行

有人会想：那我维护一个max变量，每次滑动只比较新进来的数和当前max，不就行了吗？

这里有个反例：窗口[3,1,2]，当前最大值是3；窗口右移变成[1,2,4]，移走的是最大值3。如果你只记录max = 3，新元素4比它大，还能更新成4；但如果是窗口[3,1,2]右移成[1,2,0]，移走3之后，新的最大值实际上应该是2，可你的max仍然是3，这就是错的。

所以问题的本质在于：当最大值离开窗口后，你需要立刻知道剩下的元素里“第二名”是谁。普通变量没法保存这种候选顺序，你得用一个有顺序、能两头操作的数据结构来维护候选项。双端队列就是为这个需求量身定做的。

2. 双端队列的解体思路：让候选最大值排队

2.1 为什么是Deque而不是PriorityQueue

很多刷题者第一反应是用大顶堆：每次新元素入堆，堆顶就是最大值，堆顶如果已经滑出窗口就删除。这个思路很简单，但并不是最优解。

用堆维护的最大问题是“懒删除”会留下过期元素。每次取堆顶时，你要先判断它的下标是否还在窗口内，不在就弹出；但这些过期元素可能很长一段时间都堆在堆里，占据堆顶位置后反复被弹出，内耗很大。堆的每次插入和删除都是O(log k)，总复杂度O(n log k)。

双端队列则完全不同。它可以在队首弹出过期元素，在队尾插入新元素，并且通过单调性保证队首随时就是当前窗口最大值。因为每个元素最多入队一次、出队一次，整体均摊O(1)，总复杂度O(n)。

我把两种方案的区别整理成一张表，面试时可以直接拿来解释：

2.2 单调队列维护的两个核心规则

所谓单调队列，这里特指“从队首到队尾，下标逐渐增大，元素值逐渐减小”的队列。它维护的不是窗口里的全部元素，而是“有可能成为后续窗口最大值”的候选者。

维护规则只有两条：

1. 新元素入队时，从队尾开始，把所有小于等于新元素的值全部弹出。因为这些值既没有新元素大，又比新元素更早过期，留着永远不会被选中。
2. 窗口滑动导致队首元素的下标超出窗口范围时，把队首弹出。因为窗口已经把它“送走”了，它再也没有资格参与最大值评选。

这两条规则一个负责“过期清理”，一个负责“能力淘汰”，配合起来就能让队列始终保持从大到小的递减状态。

这里特别说一下等号的处理。规则一用的是“小于等于”，也就是nums[deque.peekLast()] <= nums[i]时弹队尾。当两个元素值相等时，右边的元素下标更大，意味着它在窗口里存活时间更长，所以应该保留右边的。比如窗口里同时有下标2的值5和下标5的值5，后者更晚过期，自然更有资格替代前者。

2.3 队列里存下标而不是存值

这是好多新手写这道题时最容易犯迷糊的地方：为什么队列里不直接存int值，而非要存下标？

原因有两点：

• 判断过期需要下标。队首是否还在当前窗口内，需要拿它的下标和i - k比较，如果只存值根本没法判断。
• 比较大小也需要通过下标取原数组的值。队列里存的是下标，比较时写成nums[deque.peekLast()] <= nums[i]，取值时写成nums[deque.peekFirst()]。

其实存值也不是完全不行，但那样还必须额外存一个下标结构，两个人同时维护，操作起来更复杂。存下标其实是把“值和位置”这两个信息合二为一了，因为通过下标一定能取到值。

3. Java实现与代码逐段拆解

3.1 完整可运行的代码

先贴上完整代码，后面再逐段拆：

import java.util.ArrayDeque; import java.util.Deque; class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums == null || nums.length == 0) { return new int[0]; } int n = nums.length; int[] res = new int[n - k + 1]; Deque<Integer> deque = new ArrayDeque<>(); 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) { res[i - k + 1] = nums[deque.peekFirst()]; } } return res; } }

这段代码里有一处需要特别说明：为什么用ArrayDeque而不是LinkedList。ArrayDeque底层是循环数组，对 CPU 缓存更友好，实测表现通常比链表实现的LinkedList稳定；而且它不允许null元素，而我们队列里存的是下标，永远不会是null，所以没有副作用。JDK 的Deque接口提供了peekFirst、pollFirst、peekLast、pollLast、offerLast这些方法，正好覆盖这道题所需的所有操作。

3.2 四个关键步骤的顺序为什么不能乱

第一步“清理过期队首”放在最前面，是为了让后面对队尾的每一项操作都建立在“队列里的下标都属于当前窗口”这个前提下。如果不先清理，队首可能还残留一个已经滑出窗口的老下标；虽然它一般不影响队尾的淘汰判断，但到了读取结果的那一步就会出错。

第二步“队尾淘汰”是单调队列的灵魂。每次新来一个元素nums[i]，把队尾所有小于等于它的下标弹出。这步做掉之后，队列里的元素值从头到尾严格递减。

第三步把新下标放进队尾。由于前两步保证它一定能作为“现有最大值的候选者”合理入队。

第四步只在窗口完整时读队首。窗口从i = 0开始滑，到i = k - 1时第一个完整窗口才形成，所以条件是i >= k - 1，结果存到res[i - k + 1]。

这四个步骤的顺序我建议新手不要乱调。先清过期、再比大小、然后插入、最后读值，是一个固定模板。每一步之后队列的状态都清晰可解释，出了问题也容易定位。不是所有写法都必须这样，但这是最不容易写错的一种。

3.3 核心操作的时空复杂度推导

每个元素最多入队一次、出队一次。虽然第二步的while循环里可能连续弹出多个队尾元素，但每个元素被弹出一次也是这一次消耗了它的“出队机会”。总共入队n次，出队最多n次，所有操作加起来是O(n)，均摊到每一轮循环就是常数级别。

空间方面，队列里最多同时存在k + 1个元素吗？其实不会超过k个，因为队列里的下标都属于当前窗口，且下标严格递增。结果数组res不算额外辅助空间，所以空间复杂度是O(k)。

4. 测试与边界情况：只通过示例不够

4.1 准备一组能覆盖细节的测试用例

写算法题最忌讳“示例过了就当过了”，而是要主动构造边界用例。我把自己刷这题时用来验证的用例整理如下：

严格递增时，每个新元素都比队尾所有元素大，第二步的while会连续弹空整个队列，所以队列里通常只剩一个新下标。严格递减时，新元素永远“打不过”队尾，第二步完全不会触发，队列会一直变长，等到队首元素过期时再由第一步把它弹出去。两种情况正好覆盖了单调队列两端的核心操作。

4.2 易被忽略的边界条件

第一，数组为空或为null。代码开头直接判断nums.length == 0返回空数组，这是防御性编程的基本功。

第二，k == 1。此时每个窗口只有一个元素，最大值就是它本身。按代码逻辑走完全没问题，但你可以观察到：因为窗口长度为1，队尾淘汰会把小于等于新元素的老元素弹掉，队首又因为过期判断每轮都会被清空，队列里始终只有当前元素，结果自然等同于原数组。

第三，k == n。整个数组只有一个窗口，返回数组长度为1。代码里res长度为n - k + 1 = 1，循环结束后只会写入一次结果。

第四，nums为null时，如果直接取nums.length会抛空指针。不过力扣的测试数据通常不会给null，但养成防御习惯不是坏事。

4.3 手动画一遍队列变化，比背答案管用

我建议刷这道题时，拿[1,3,-1,-3,5,3,6,7]，k=3，亲手画一遍单调队列的变化过程。

i=0：队列空，1入队，队列[0]，此时i < 2不写结果。

i=1：队首0未过期；队尾比较1 <= 3，弹出下标0；1入队，队列[1]。

i=2：队首未过期；队尾比较3 <= -1不成立；2入队，队列[1,2]；窗口完整，队首1对应值3，写入res[0]=3。

i=3：队首1刚好等于i-k=0？不对，i-k=0，队首是1，没过期；队尾比较-1 <= -3不成立；3入队，队列[1,2,3]；取队首3，写入res[1]=3。

走到i=4：队首1的下标等于1，当前窗口左边界是i-k+1=2，说明下标1已经滑出窗口，第一步弹掉；第二步比较-3 <= 5、-1 <= 5、3 <= 5，一口气弹出3、2、1；然后4入队；写入res[2]=5。

你会发现每一步都符合“队首即最大”的预期。只要把这个过程在纸上演练一遍，代码里四个步骤的顺序和目的就全都通了。

5. 面试追问与常见错误，能答透才说明真会

5.1 追问一：为什么时间复杂度是O(n)而不是O(n*k)

这是面试官最常追问的点，其实答案就一句话：每个元素入队一次、出队一次，所有操作次数之和不超过2n。

很多人误以为第二步的while循环可能在每一轮都弹出多个元素，所以不是线性的。但一个元素一旦被弹出，后面就不会再进队了；它能被弹的次数就是它自己的那一次“出队”。把视角从“每轮循环做了什么”切换到“每个元素被操作了几次”，就明白均摊复杂度是线性的。

5.2 追问二：能不能用堆做，两个方案怎么选

堆方案适合面试时先说思路，因为它直观：维护一个大顶堆，堆里存(值, 下标)，每次新元素入堆，弹出堆顶直到堆顶下标还在窗口内。代码写起来也短，但复杂度是O(n log k)，而且堆里的过期元素偶尔会堆积到接近n个，空间表现差。

如果面试官追问“能不能优化”，就应该给出双端队列单调队列方案。如果笔试环境时间紧张，先用堆快速拿到通过也不是不行，但面试手撕代码时，我推荐直接上单调队列，因为面试官对这道题的期待就是看到你能写出线性方案。

5.3 追问三：如果数据是流式的，k很大怎么办

双端队列解法天然支持流式场景，因为每个元素只在它到达时处理一次，而且队列长度最多是k。即使k很大，只要内存能放下k个下标，就没问题。

如果k大到连队列都放不下，那就得换思路了。比如分块预计算、稀疏表之类的方案，但那些往往要求数据可以离线处理，不适合流式场景。面试中把这句话讲清楚，基本就能体现你对这个问题的理解深度。

5.4 我踩过的坑和教训

第一坑：过期判断的边界。窗口左边界是i - k + 1，所以队首下标<= i - k时必须删除。我曾经写过deque.peekFirst() < i - k，结果最大值晚了一格才被移出，返回结果里出现了已经不属于窗口的旧最大值。这个问题很隐蔽，小数组测不出来，一旦出现连续多个小元素夹着旧最大值的情况就会暴露。

第二坑：写结果之前忘记判断窗口是否完整。如果不加i >= k - 1就直接取队首，前面k-1个不完整窗口也会被当成结果写进数组，导致结果长度错乱。

第三坑：队尾淘汰时用了<而不是<=。结果可能依然全对，但如果面试官追问“相等的值你保留哪个、为什么”，答不上来就很尴尬。养成写<=的习惯，遇到重复值保留更靠右的元素，逻辑更稳。

第四坑：用LinkedList或ArrayDeque时，调用getFirst()、getLast()前不判空。空队列调用会抛NoSuchElementException，用peekFirst()和peekLast()配合isEmpty()更安全。

最后分享一个我自己的做题习惯。拿到滑动窗口相关题目，先把窗口左边界公式i - k + 1写在注释里，再写四步循环骨架。写完之后至少跑四组用例：k=1、k=n、全相同、完全逆序，基本能覆盖所有隐藏边界。这道题的精髓不是背代码，而是理解“能力淘汰”和“过期清理”这两个动作，在窗口滑动的每一轮里双向维护队列。只要把队列变化过程画明白，面试现场哪怕一时卡壳，也能顺着队首、队尾的进出逻辑把代码推导出来。