企业官网建设流程全解析

力扣239这道题，我几乎每次给人讲单调队列的时候都会拿出来当入门案例。题目本身不复杂——给你一个数组和一个窗口大小k，窗口每向右移动一格，让你返回每个窗口里的最大值。可就是这么一道题，能让很多人从暴力解一路优化到双端队列，在边界条件里踩出各种坑。这篇文章就围绕“滑动窗口最大值”这个场景，用Java的ArrayDeque把双端队列解法彻底讲透：为什么它能做到O(n)、代码怎么写、有哪些特别容易出错的地方。适合正在刷题准备面试的朋友，也适合想真正搞懂单调队列这个数据结构、而不只是背一道题的人。如果你现在看到这题的第一反应是“每个窗口扫一遍”，那正好，这篇文章会把你的复杂度从O(nk)拉下来，思路理清之后，同类题目基本都能顺手解掉。

1. 题目到底在问什么：先把这个“窗口”看透

1.1 一句话理解滑动窗口最大值

题目给的是一维数组nums，比如[1, 3, -1, -3, 5, 3, 6, 7]，窗口大小k=3。窗口从左往右滑动，每次移动一个位置。所谓“窗口”就是数组中固定长度的一段区间，第一个窗口覆盖下标0到2，第二个窗口覆盖下标1到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 - k + 1。这个推导很简单：数组有n个元素，窗口长度是k，从第一个元素开始每次向右移动一格，最后一个窗口的起点是n - k，所以窗口数量是n - k + 1。写代码时结果数组的长度直接用这个公式，别写成n，也别写成n - k。

这道题在面试里属于高频题，因为它的考察点很集中：数组遍历、数据结构的选用、边界条件的处理、时间复杂度优化。暴力解法人人都能写出来，但最优解能不能想到、能不能把细节写对，才是拉开差距的地方。

1.2 暴力解法为什么不行

最直接的解法，就是对每个窗口都从头到尾扫描一边，找最大值。伪代码很简单：外层循环枚举窗口起点i，从0到n - k，内层循环从i到i + k - 1扫一遍，维护一个max变量。

时间复杂度怎么算？外层大约n - k + 1个窗口，每个窗口内扫描k个元素，总操作次数约(n - k + 1) * k。当k约等于n/2时，这个值大约是O(n²/4)。如果n是10的5次方，那就要跑大约25亿次比较，在多数评测环境下直接超时。就算k比较小，比如k=10、n=10的5次方，也要做约100万次操作，能过但完全谈不上优雅。

暴力解法的问题在于完全没有利用窗口滑动过程中“相邻窗口之间只有两个位置发生变化”这个事实。窗口从下标0~k-1移到1~k，右边多了一个新元素nums[k]，左边少了一个旧元素nums[0]。如果求的是窗口内所有元素的和，那很好办：新窗口和 = 旧窗口和 + 新进来的数 - 出去的数，O(1)就能更新。但最大值不行，因为如果出去的那个元素恰好是当前窗口的最大值，你没法立刻知道下一个最大值是多少，还得重新比较。这个“删除最大值后如何快速找到次大值”的问题，正是接下来所有优化方案要解决的核心矛盾。

2. 双端队列解法的核心思路：不止是数据结构，更是策略

2.1 为什么非要用双端队列

面对“维护窗口最大值，同时要支持左边删元素、右边加元素”这个需求，需要想一想什么样的数据结构合适。

• 普通队列：先进先出，支持队尾进、队首出，但取最大值还是得遍历，不行。
• 优先队列（堆）：堆顶能O(1)拿到当前最大元素，但问题在于元素过期后，堆顶如果是过期元素，你不知道该不该把它删掉、删掉之后下一个元素是谁，通常需要“惰性删除”——堆里同时存值和下标，取结果时不断弹出堆顶直到堆顶下标仍然在窗口内。这样做复杂度是O(n log k)，能过题，但不是最优。
• 双端队列：两头都能进出，还能在两端都做O(1)的查看和删除操作。这个特性刚好匹配滑动窗口的需求——右边进新元素，左边出过期元素。如果再配合“单调性”的维护策略，队首始终是当前窗口最大值，那么读取答案也是O(1)。

这里的核心其实不是“双端队列”这个容器本身，而是“单调”这个维护策略。所谓单调队列，就是让队列里的元素值从队首到队尾保持单调递减。队首是当前窗口的最大值的候选，队尾是当前窗口里“最弱”的候选。如果队列始终保持单调递减，那队首元素就直接是答案。

还记得前面提到的核心矛盾吗？最大值被移除后怎么找下一个最大值？单调队列的答案是：在维护队列时，把所有“在未来不可能成为最大值”的元素提前淘汰掉，队列里留下的都是“还有希望”的候选。这样即使最大值滑出窗口，队列里剩下的队首就是下一个最大值。

2.2 单调性的维护规则：一句话就能说清

规则不难，每次处理新元素nums[i]的时候做三件事：

1. 检查队首的下标是否已经滑出当前窗口。当前窗口的左边界是i - k + 1，如果队首的下标小于这个值，说明它已经不在窗口里了，从队首弹出。
2. 从队尾开始，把所有值小于等于nums[i]的元素弹出。因为这些旧元素既比新元素小，又比新元素更早离开窗口，在各自的剩余生命周期里都不可能是最大值。
3. 把当前下标i从队尾入队。此时队列仍然保持从队首到队尾单调递减的状态。

一句话总结就是：入队前，把队尾所有“又老又弱”的元素清掉；记录答案前，把队首所有“过期”的元素清出去。这个策略的本质是，在维护一个“候选最大值池”，池子里只保留有可能在某个窗口里成为最大值的元素。

用生活场景类比一下：想象窗口是一排座席，每次新来一个人，他要从队尾往队首方向打量。如果发现前排有人比他弱、还比他先离场，那这个人就没必要留在候选名单里了，直接请出去。新人入座后，再看看队首那个最强的人是不是已经到点离场了，如果离场了他也被请走。这时候队伍最前面的那个人，就是当前窗口里最强的人。

这个策略妙在，每个元素最多入队一次、出队一次，所以虽然看起来每次入队前可能要弹出好几个元素，但所有弹出操作加起来不会超过n次。整体复杂度是O(n)，而不是很多人第一眼理解的O(nk)。

2.3 为什么存下标而不直接存值

这是这道题最容易踩的坑之一。很多人第一次写单调队列的时候，会想当然地在队列里存入数本身，比如把“3”这个值放进队列。问题是，窗口滑动的时候，队列里的“过期元素”不仅需要判断值的大小，还需要知道它的位置。如果只存值，你根本不知道这个值是数组里哪个位置的，也就无法判断它是否还在当前窗口内。

存下标的好处有两个：

第一个好处是可以通过下标直接取到对应的值，nums[index]就是O(1)操作，不会丢失信息。第二个好处是判断元素是否过期非常方便：窗口左边界是i - k + 1，队列里存的下标只要小于这个值，就说明它已经滑出了窗口。这个判断是纯粹的整数比较，没有任何额外查询成本。

这一点和“单调栈”不太一样。单调栈通常不关心元素的生命周期，元素入栈后不会因为“过期”被强制移出，它出栈只是因为遇到了更大的元素。而滑动窗口中的元素有明确的存活窗口，超过窗口就必须被清理。所以这里必须存下标，这是由场景决定的。

3. Java实现与逐段拆解：代码要怎么落到Java上

3.1 完整代码：双端队列解法

直接用Java实现，核心数据结构用ArrayDeque。完整代码如下：

import java.util.ArrayDeque; import java.util.Deque; public class SlidingWindowMax { public int[] maxSlidingWindow(int[] nums, int k) { if (nums == null || nums.length == 0) { return new int[0]; } int n = nums.length; int[] ans = new int[n - k + 1]; // 队列里存的是下标，不是元素值 Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // 第一步：清理队首，移除已经滑出窗口的下标 if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { deque.pollFirst(); } // 第二步：清理队尾，弹出所有小于等于当前元素的旧下标 while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) { deque.pollLast(); } // 第三步：当前下标入队尾 deque.offerLast(i); // 第四步：窗口已形成，记录队首对应的值 if (i >= k - 1) { ans[i - k + 1] = nums[deque.peekFirst()]; } } return ans; } }

这个代码之所以能保持O(n)，关键点在于第二步。while循环里可能连续弹出多个元素，但这些元素一旦弹出就不会再入队。每个元素最多处理两次（入队一次、出队一次），所以所有while循环的总花费是O(n)，不是每次循环都扫描k个元素。

Java的ArrayDeque有几个方法需要注意：peekFirst查看队首元素但不弹出，pollFirst弹出队首元素，peekLast查看队尾元素，pollLast弹出队尾元素，offerLast把元素加到队尾。这几个方法都是O(1)。ArrayDeque不允许存储null元素，但这里队列里存的是数组下标，都是整数，不存在null问题。也可以用LinkedList替代，它们行为相似，但ArrayDeque在大多数场景下内存更紧凑、性能更好，所以优先用它。

3.2 四步循环为什么是这个顺序

经常有人问我，代码里的四步能不能换顺序？先说结论：标准顺序是“清队首过期元素 → 清队尾弱元素 → 入队 → 记录答案”，这样最不容易出错。

先清理队首，是因为我们要保证后续操作中，队列里的所有元素都在当前窗口内。如果队首已经过期，但它还留在队列里，后面的比较和记录都是以它为基础的，容易产生逻辑混乱。比如记录答案时，队首如果是个过期下标，一取就是错误的res。所以第一步先清理，一旦队首滑出窗口，立即弹出。

第二步清理队尾，是为了保持单调性。新元素入队之前，把队尾所有“小于等于新元素”的候选清掉，这样队列从队首到队尾一定保持递减。第三步再入队，队列的单调性和合法性就都维护好了。

有人可能觉得“先清队尾再入队、最后清队首”也能得到正确答案。确实，在某些场景下也能通过测试，因为最终在记录答案前，队首过期元素始终会被清理掉。但这样做需要反复确认每一次操作后队列状态是否正确，尤其在面试现场，容易把自己绕晕。作为通用模板，还是应该按照“清过期、清弱元素、入队、记录”这个顺序来，简洁且可靠，既容易记忆，也容易向面试官解释。

3.3 手动跑一遍完整流程

用之前的例子验证代码逻辑：nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3。

第一轮，i=0，nums[0]=1：队列空，无需过期处理；队尾无元素可弹；入队下标0；i < k-1，不记录。队列状态：[0]（值1）。

第二轮，i=1，nums[1]=3：先清过期，队首0不小于-1，保留；队尾下标0的值1 <= 3，弹出；队列空，入队下标1；i=1 < 2，不记录。队列状态：[1]（值3）。

第三轮，i=2，nums[2]=-1：队首下标1不小于0，保留；队尾值3 > -1，不弹；入队下标2；i >= 2，记录队首nums[1]=3，ans[0]=3。队列状态：[1(3), 2(-1)]。

第四轮，i=3，nums[3]=-3：队首1不小于1，保留；队尾-1 > -3，不弹；入队下标3；记录ans[1]=3。队列状态：[1(3), 2(-1), 3(-3)]。

第五轮，i=4，nums[4]=5：队首1不小于2，保留；从队尾开始，下标3的值-3 <= 5弹出，下标2的值-1 <= 5弹出，下标1的值3 <= 5弹出；队列空，入队下标4；记录ans[2]=5。队列状态：[4(5)]。

第六轮，i=5，nums[5]=3：队首4不小于3，保留；队尾值5 > 3，不弹；入队下标5；记录ans[3]=5。队列状态：[4(5), 5(3)]。

第七轮，i=6，nums[6]=6：队首4不小于4，保留；队尾值3 <= 6弹出，队尾值5 <= 6弹出；入队下标6；记录ans[4]=6。队列状态：[6(6)]。

第八轮，i=7，nums[7]=7：队首6不小于5，保留；队尾值6 <= 7弹出；入队下标7；记录ans[5]=7。队列状态：[7(7)]。

最终结果ans = [3, 3, 5, 5, 6, 7]，和手算一致。整个过程里每个下标最多入队一次、出队一次，复杂度就是O(n)。这个手动过程建议在纸上自己推一遍，推完你对这段代码的信任度会高很多。

3.4 边界条件的推导：i - k + 1是怎么来的

很多代码能写出来，但解释不清楚边界。当前遍历到下标i时，窗口的范围应该是[i - k + 1, i]。为什么左边界是i - k + 1？因为窗口长度固定为k，右边界是i，窗口内共有从i - k + 1到i这k个元素。比如k=3、i=2，窗口就是0到2，左边界确实是0；i=3，窗口就是1到3，左边界是1。

判断队首是否过期的条件就是deque.peekFirst() < i - k + 1。注意这里是严格小于，而不是小于等于。因为等于左边界时，该元素正好是窗口内最左边的一个元素，仍然属于当前窗口，不应该被弹出。弹出它，你就丢掉了当前窗口的合法最大值候选。

当i还很小、窗口尚未完全形成时，比如k=3、i=1，左边界是-1，没有哪个下标会小于-1，所以不会误弹出任何元素。这说明这条判断语句在窗口未成形时也是安全的，不需要额外加一个if保护。上面代码里把它放在所有循环的每一步，天然就符合逻辑。

4. 高频踩坑与常见问题排查：这些坑我基本都踩过

4.1 队列里存值不存下标

这是最典型的问题。如果你在队列里直接存元素值，而不是存下标，运行到需要判断“队首是否过期”的时候就会发现没法判断了。你只知道队首的值是几，但不知道它是数组里哪个位置的值，也就不知道它还在不在窗口里。

表现出的现象是：滑动几次窗口之后，结果开始错乱，尤其是遇到“旧最大值本该被移出窗口但还留在队列里”的时候，输出里会出现已经不在窗口内的旧值。

修正方法就是把队列改成存下标，需要比较值的时候通过nums[deque.peekLast()]来取值。这看似绕了一步，其实是解决“过期”问题最直接的手段。记住一句话：只要涉及窗口内元素的生命周期，就一定要存下标。

4.2 相等值时用“<”还是“<=”

来看清理队尾那条while循环的条件：

nums[deque.peekLast()] <= nums[i]

这里的<=非常讲究。如果用<，遇到连续相同的元素时，比如[3, 3, 3, 3]，k=2，队列里会堆积多个值相同的下标。虽然队首还是最大值，不会导致最终结果错误，但队列长度会很臃肿，而且每个相同值的旧下标都要等着被“过期”弹出，白白增加了操作次数。

用<=的好处是：当新元素和队尾元素值相等时，直接弹出旧下标，保留新下标。新下标更靠右，离窗口右边界更近，生命周期更长，能覆盖后续更多的窗口。反正值都一样，队首取哪一个都是最大值，那为什么不留下一个更晚过期的呢？这个细节很多人不注意，面试时能主动提出来，反而是加分项。

4.3 第三步入队和第二步清理队尾搞混导致的问题

还有人会写成“入队 → 清队尾 → 清队首 → 记录答案”。比如先把当前下标放进队列，再回头清理。这种顺序偶尔也能跑出正确答案，但不能保证所有场景下都正确。关键是它破坏了“队列里永远只保留当前窗口候选项”的直观语义，一旦队首过期后队里还有多个过期元素，你得连续弹出好几次才能找到有效值，逻辑容易失控。

也不要写成“清队尾 → 入队 → 记录 → 清队首”。如果在记录答案之前不清队首，那么当队首已经滑出窗口时，你记录到的就是过期元素，结果必然出错。有的代码会把清队首放到最后一步，那记录答案的时间点就得放在清队首之后。不同写法的可行性和正确性确实有差异，用标准四步顺序最保险。

4.4 结果数组初始化和空数组处理

结果数组的初始化有个常见错误：有人习惯把数组初始化为0，但如果数组里全是负数，0就会比真实最大值还大，导致结果错误。正确做法是直接在循环里给ans[i - k + 1]赋值，不要依赖默认值。如果nums为空，直接返回new int[0]，否则后面计算n - k + 1时会得到负数或异常值。另外k=1时，每个窗口只有一个元素，结果就是数组本身，这段代码也能正确返回，不需要单独处理。但kotlin好一点，这层的逻辑在Java里就得自己保证。

4.5 调试与对拍技巧

如果在本地调试这道题，我建议你写一个暴力解法作为基准，然后随机生成小数组，把两种解法结果对比。这种做法叫对拍，能快速发现逻辑错误。对拍代码不需要多复杂：写一个bruteForce(int[] nums, int k)方法，每个窗口扫一遍取最大值；再写一个maxSlidingWindow调用单调队列解法；最后用Random生成长度不超过20的数组，循环几千次比较结果。

一旦发现不一致，就打印当前的nums、k、两个方法的结果，再把i循环里每轮的队列状态打印出来。队列状态打印的代码可以这样写：

System.out.println("i=" + i + " deque=" + deque + " values=" + deque.stream().map(idx -> nums[idx]).collect(Collectors.toList()));

看到queue里的下标序列和值序列，基本就能定位是哪一步的清理条件写错了。我自己的经验是：先查过期条件的小于号方向，再查清理队尾的比较符号，最后查入队顺序。九成以上问题都出在这三个地方。把常见错误整理成一张速查表：

5. 从一道题到一类题：单调队列的延伸与我的实战建议

5.1 单调队列的通用模板

滑动窗口最大值这套思路其实是一个模板，遇到“滑动窗口内的最值”类问题都可以套。模板就四步：

1. 清理队首过期元素：deque.peekFirst() < i - k + 1时弹出。
2. 清理队尾弱元素：比较值后从队尾弹出。
3. 当前下标入队。
4. 窗口形成后记录队首对应的值。

不同题目最大的差异在第二步的比较方向。求滑动窗口最大值，队列保持单调递减，队首最大，清理队尾时条件是nums[deque.peekLast()] <= nums[i]。如果是求滑动窗口最小值，就把队列改成单调递增，队首是最小值，清理队尾时条件是nums[deque.peekLast()] >= nums[i]。

还有一些题目不直接给窗口大小k，而是让你求“长度不超过某值的子数组最优解”，这时候往往要把“边界条件”从固定长度改成动态限制条件，思路框架不变，但判断是否过期的条件要跟着调整。比如求长度不超过k的子数组的最大平均值，配合前缀和与单调队列就经常是标答。遇到这类题不用慌，先问自己三个问题：窗口范围怎么界定？哪个方向保持单调？队首元素能直接作为答案吗？这三个问题想清楚，核心逻辑就出来了。

5.2 为什么每个元素最多进出一次：复杂度证明

再说一次时间复杂度，这是面试必问。每个元素在第一次被扫描到时，如果队列满足条件，它会被offerLast入队；之后它可能因为滑出窗口被pollFirst弹出，也可能因为遇到更大的新元素被从队尾pollLast弹出。无论哪种情况，每个元素最多入队一次、出队一次，所以所有入队出队操作加起来是O(n)的。就算while循环看起来可能弹出很多元素，但这些弹出次数在所有循环中累计起来不超过n，因此总代价是线性的。

空间复杂度是O(k)，因为队列里最多同时保留k个候选下标。考虑极端情况：数组严格递减，比如[5,4,3,2,1]，k=5，这时队列里会保留全部5个下标，因为没有任何一个元素会被更小的元素淘汰。所以队列长度上限就是窗口大小k，不会超过k。

理解“每个元素最多进出一次”这一点，才算真正理解为什么这个解法是O(n)。如果你对面试官复述不出这一层，那就说明你还没完全吃透。

5.3 我的实战体会：把状态图亲手画一遍

我个人的建议是，刷这道题的时候不要急着看题解，先自己拿纸笔画几轮队列变换。画的过程里，你会自然地把“过期”和“淘汰”两个动作区分开，特别不容易忘。

我当年自己刷这道题，第一次写出代码后跑测试用例，前几个能通过，遇到一个倒序数组反而错了。当时把队列状态打印出来才发现，问题出在我用<而不是<=清理队尾，导致相同最大值的情况下队列里堆积了太多旧下标，一个过期之后还要连续弹好几个才能找到下一个有效候选。从那以后，我凡是遇到“窗口内极值”相关的题，都会先问自己一句：“是不是该用单调队列？队列里存下标还是值？比较的时候用小于还是小于等于？”这三个问题问完，代码基本就能写对了。

后来面试遇到这道题，我一般会先给暴力解法，再解释暴力为什么慢，然后引出单调队列。很多面试官会在你写完代码之后追问“为什么时间复杂度是O(n)”，如果前面把数据结构选的思路讲清楚了，这个问题其实很自然就能答上来。这也是我把这道题作为“面试重灾区”推荐给大家的原因——它覆盖面广、解法经典、细节密度高，认真吃透一道题，顶得上盲目刷十道简单题。