企业官网建设流程全解析

剑指offer-64这道题，在我刷了三遍之后，终于敢说彻底吃透了。滑动窗口最大值，说白了就是给你一个数组和一个固定长度的窗口，窗口从左往右滑，每滑一步都问你这个窗口里最大的数是几。LeetCode上对应的是239题，难度分类是困难，但实际掌握了单调队列的思路后，你会发现它其实是被“困难”两个字吓住了很多人，核心代码也就二十来行。这篇文章我准备把这道题从暴力解法到单调队列优化，从代码实现到面试追问，一次性讲透，适合正在刷题准备面试的朋友，也适合刚学完数据结构想找实战场景的初学者。

我第一次做这道题的时候，其实是被“困难”标签唬住的。后来想明白了，这题考察的就两件事：一是你懂不懂滑动窗口这个模型，二是你知不知道单调队列这种优化手段。这两个点一旦拆开，整道题的骨架就露出来了。先别急着看答案，我建议你按下面的思路一步步推，推到哪一步卡住了，再回头看我的讲解，印象会深很多。

1. 题目拆解：先搞清楚滑动窗口最大值到底在考什么

1.1 从暴力解法入手，先知道基线在哪里

很多人一上来就想着最优解，结果自己把自己绕晕了。我个人的习惯是，拿到题先写一个最直白的解法，哪怕复杂度很烂，至少能保证答案是对的，然后再去想怎么优化。

这道题的暴力解法非常直观：窗口从0位置开始，每次计算当前窗口范围[i, i+k-1]内的最大值，然后窗口右移一格。窗口一共会移动n-k+1次，每次扫描k个元素找最大值，所以时间复杂度是O(nk)。

public int[] maxSlidingWindow(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 + 1; j < i + k; j++) { max = Math.max(max, nums[j]); } res[i] = max; } return res; }

这个代码在n和k都比较小的时候是能跑的，但一旦n到10万、k到5万，双层循环就会慢到让人怀疑人生。面试的时候写这个版本，基本等于告诉面试官“我只会暴力”。

不过暴力版本的价值在于，它帮我们把问题的计算瓶颈暴露出来了：窗口每次只移动一格，但我们在重复扫描窗口里的大部分元素，明明上一次已经看过的数字，这次又要重新比一遍。如果可以设计一种数据结构，让窗口内的最大值能“动态”维护，每次滑动只需要很小的代价就能拿到结果，那性能就上去了。

1.2 单调队列的核心思路：为什么它高效

顺着刚才的瓶颈往下想，我们会希望：窗口滑动的时候，新元素加进来，旧元素出去，最大值这个信息能被增量地维护，而不是全量重算。

一个很自然的想法是维护一个“候选最大值”的集合。每次窗口滑动，我们做两步操作：第一步，把窗口最左边滑出去的那个元素从集合里删掉；第二步，把新进入窗口的元素加进去；然后，集合里的最大值就是答案。

问题来了：用什么集合能做到新增、删除、取最大值都快？堆（优先队列）可以做到，Java的PriorityQueue删除任意元素是O(k)的，整体复杂度不稳定。有没有更巧妙的办法？

这里有一个非常关键的观察：如果窗口里有a和b两个元素，a在b的左边，但a的值比b小，那么只要b还活着，a就永远不可能是这个窗口的最大值。因为窗口是向右滑的，a一定比b更早离开窗口。换句话说，a是一个“永远卷不过b”的候选人，留着它只会浪费时间。

把这个观察用起来，我们可以在窗口内维护一个从队头到队尾单调递减的队列。队列里存的都是“有可能成为窗口最大值”的元素，而且它们是从大到小排好队的。队头就是当前窗口的最大值。

当新元素x要入队时，我们不停地把队尾那些比x小的元素弹出，因为它们不可能再翻身当老大了。然后再把x放到队尾。这样队列始终保持着从大到小的顺序。这个思想就叫“单调队列”，它保证了每个元素最多入队一次、出队一次，平均到每次滑动，代价是O(1)。

2. 双端队列实现：从原理到代码

2.1 双端队列为什么是天然适配的数据结构

单调队列这个思路确定后，就要选数据结构了。它的操作特点是很明确的：需要在队尾弹出元素（淘汰小值）、在队尾加入元素（新元素入队）、在队头弹出元素（窗口左边界滑出）、读取队头元素（拿最大值）。

这四个操作，正好对应双端队列Deque的能力。Java里可以这样声明：

Deque<Integer> deque = new ArrayDeque<>();

ArrayDeque底层是循环数组，读写效率高，不允放空值，在这个场景下够用了。当然也可以用LinkedList，也是双端队列的实现，但常数上略慢一点。

这里有一个细节，队列里存的不是数组值本身，而是元素在数组里的下标。为什么要存下标而不是值？因为窗口滑动的时候，我们需要知道队头元素是不是已经滑出窗口了。只有知道下标，才能判断deque.peekFirst() < i - k + 1，也就是队头元素是否已经不在当前窗口范围内。如果只存值，这个判断就无法完成。这个点我在第三部分还会展开说。

2.2 完整代码实现，Java和Python都给你

下面是我在面试中比较喜欢的写法，逻辑清晰，边界也容易处理。先看Java版本：

public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n == 0 || k == 0) { return new int[0]; } int[] res = new int[n - k + 1]; Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // 1. 弹出队头滑出窗口的元素 if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { 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; }

Python版本核心逻辑一模一样：

from collections import deque def maxSlidingWindow(nums, k): n = len(nums) if n == 0 or k == 0: return [] res = [] dq = deque() for i in range(n): # 弹出队头滑出窗口的元素 if dq and dq[0] < i - k + 1: dq.popleft() # 弹出队尾所有比当前元素小的元素 while dq and nums[dq[-1]] <= nums[i]: dq.pop() dq.append(i) # 窗口形成后，收集结果 if i >= k - 1: res.append(nums[dq[0]]) return res

这段代码的循环里一共有四个动作，顺序很重要：先清理过期元素，再淘汰队尾小值，然后入队，最后取结果。很多人写的时候会把第2步和第1步反了，或者漏掉第1步，就会出一些看起来很奇怪的bug，稍后我在第四部分专门列几个踩坑案例。

3. 核心细节与复杂度分析：别只背代码，要懂为什么

3.1 为什么队列里存下标而不是值

这个点面试官特别喜欢问。如果只存值，当队头元素滑出窗口时，你无法知道它到底应不应该离开；更麻烦的是，如果窗口里有重复值，只存值会导致你根本分不清哪个值先来后到。存下标就能精确地做两个判断：一是nums[i]和nums[deque.peekLast()]比较大小；二是deque.peekFirst()是否小于i - k + 1来判断队头是否已经越界。

这里还有一个细节：while循环里，比较用的是<=还是<？我写的是<=，也就是当队尾元素和当前新元素相等时，把队尾元素弹出去，让新元素入队。这样做对吗？是对的。因为两个相等的元素，下标更大的那个存活时间更长，更适合作为候选最大值。把旧相等元素淘汰掉，不需要额外付出任何代价，还让队列里存储的元素更“新鲜”。如果写<，旧相等元素就会一直留在队列里，但因为它和新元素值一样大、又更早离开窗口，等旧元素滑出时就很尴尬，等于留了一个没用的候选者。所以遇到相等值，直接让新的淘汰旧的，代码更干净。

3.2 初始化窗口与滑动过程的统一写法

很多资料的写法是分两步：先把第一个窗口的k个元素处理完，再开始滑动收集结果。这样写也没问题，但要多写一段重复逻辑，代码不够紧凑。

我更喜欢上面的写法：从头到尾只用一次循环，在循环里用i >= k - 1作为“窗口是否已经形成”的判断条件。前k-1个元素的时候，只做入队和维护操作，不输出结果；从第k-1个元素开始，每轮都输出一个结果。这个统一写法可以减少代码分支，也降低了漏写情况的概率。

我们来手推一遍，用数组[1, 3, -1, -3, 5, 3, 6, 7]，k = 3：

• i=0，元素1，队列为空，入队。队列：[0(1)]。i < 2，不输出。
• i=1，元素3，队尾1比3小，弹出；入队1(3)。队列：[1(3)]。i < 2，不输出。
• i=2，元素-1，队尾3比-1大，保留；入队2(-1)。队列：[1(3), 2(-1)]。窗口形成，输出nums[队头]=3。结果：[3]。
• i=3，元素-3，队头下标1仍满足>= 1，不出队；队尾-1比-3大，保留；入队3(-3)。队列：[1(3), 2(-1), 3(-3)]。输出3。结果：[3, 3]。
• i=4，元素5，此时窗口范围是[2,4]，队头下标1已经小于2，出队；然后队尾-3、-1、3全都比5小，依次弹出；入队4(5)。队列：[4(5)]。输出5。结果：[3, 3, 5]。
• i=5，元素3，队头4满足>= 3；队尾5比3大，保留；入队5(3)。队列：[4(5), 5(3)]。输出5。结果：[3, 3, 5, 5]。
• i=6，元素6，队尾3、5都比6小，依次弹出；入队6(6)。队列：[6(6)]。输出6。结果：[3, 3, 5, 5, 6]。
• i=7，元素7，队尾6比7小，弹出；入队7(7)。队列：[7(7)]。输出7。结果：[3, 3, 5, 5, 6, 7]。

推一遍下来，整个逻辑就非常直观了。你会发现队列里的元素始终保持单调递减的顺序，队头永远是当前窗口最大值。

3.3 复杂度推导

时间复杂度上，每个元素最多入队一次、出队一次，出队动作可能发生在队头也可能发生在队尾，但总数不会超过n次。所以整个循环的总操作次数是O(n)，均摊到每次滑动就是常数时间。空间复杂度是O(k)，因为队列里最多同时存k个元素，有些情况下队列长度可能比k小很多（比如数组严格递减时，队列会一直累积到k个；数组严格递增时，队列始终只有1个元素），但最坏情况不会超过k。对比之前暴力解法的O(nk)，这是一个质的飞跃。

这里我想多说一句复杂度分析的心得。很多人觉得复杂度分析就是背结论，其实不是。像这道题，你要想明白为什么均摊是O(1)，关键就在于“每个元素只被处理两次”这个事实。这类“虽然看上去循环里有循环，但每个元素进出一次”的套路，在很多单调栈/单调队列题目里都会出现，理解了它，你以后做接雨水、柱状图最大矩形这类题也会顺手很多。

4. 常见坑点与排查技巧实录

4.1 边界条件相关的坑

第一道坑是k比n大，或者k等于0、数组为空。我刚开始写的时候没加这个判断，结果在一些极端测试用例上直接数组越界。稳妥的做法是函数一进来就判空：

if (n == 0 || k == 0) { return new int[0]; }

有些题里也可能出现k大于n的情况，严格来说这种用例不合规，但还是防御性处理一下比较好。

第二个坑是队列清理过期元素的时机。我见过有人先把新元素入队，然后再去清理队头，这样在极端情况下会把正常元素误删。顺序必须是：先判断队头是否过期，再淘汰队尾小值，再入队，再取结果。这个顺序一旦打乱，调试起来非常痛苦，因为问题不是必现，而是取决于具体的数组排列。

第三个坑是while循环里比较的是下标还是值，这个比较容易搞混。nums[deque.peekLast()]才是值，deque.peekLast()是下标。如果直接拿元素值和下标比，在数组元素刚好在0附近时会得到完全错误的结果。

第四个坑是Java的ArrayDeque不允许存储null，但这道题我们存的是下标，所以不会遇到null问题。不过你要是复用了这段代码去处理别的场景，被提醒一下总是好的。

4.2 面试时的几个关键追问

面试官在考察这道题的时候，通常不会只让你把代码写出来。至少这几个问题是常问的：

第一个问题：为什么用双端队列而不是优先队列？答案是优先队列的删除操作需要先找到那个元素再删除，时间复杂度是O(k)，而双端队列能让所有操作都变成O(1)。面试官如果继续追问，你就需要解释清楚“每个元素最多进出队列一次”的均摊代价。

第二个问题：如果要求输出每个窗口的最小值，怎么改？很简单，把单调队列的单调性反过来，从队头到队尾单调递增，队头就是最小值。代码几乎不用变，只需要把<=改成>=，也就是淘汰队尾所有比当前元素大的元素。

第三个问题：如果数组是流式的，也就是数据一个一个到达，不知道总长度，还能做吗？可以。这就是滑动窗口限流的底层思路之一。我们不需要知道n，只需要维护一个窗口起始位置left，每次新元素到达时，先清理小于left的队头，再按同样的逻辑维护队列。这个变体和剑指offer原题是同一个核心。

第四个问题：这个算法和TCP流量控制里的滑动窗口是一回事吗？这是新手容易混淆的地方。TCP的滑动窗口是流量控制模型，目的是协调发送端和接收端的速率；这里的滑动窗口是算法题里的固定窗口扫描模型。两者只是名字里都有“滑动窗口”，本质上不是一回事。面试时如果你的简历里有网络相关的项目，面试官可能会顺带问一句，最好能分清楚。

4.3 变体与扩展

这道题背后藏的是一类问题：滑动窗口 + 单调性查询。掌握了单调队列，下面这些题目你都能很快想到思路：

• 求每个窗口的最小值：把单调性反过来。
• 求每个窗口的最大值和最小值之差（极差）：同时维护两个单调队列，一个递增一个递减。
• 求满足条件的最短/最长子数组：用双指针维护窗口，配合单调队列求窗口内的最值。
• 环形数组上类似的窗口问题：把数组复制一份接在后面，再套同样的模板。

我之前在项目里还用过这个思路做实时数据的峰值检测，比如采集一段传感器数据，想知道每秒钟内温度的最高值和最低值，就是典型的滑动窗口最值问题。这类算法不只是面试题，工程里也经常派上用场。

4.4 一个容易被忽视的细节：用while而不是if清理队尾

我见过很多初学写法是：

if (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) { deque.pollLast(); }

这里用if是有问题的。因为队尾可能存在多个比当前元素小的元素，必须通过while循环把它们都弹掉，直到队尾元素比当前元素大为止。如果只弹一次，队列的单调性就被破坏了，队头有概率不是最大值。这也是为什么我强调要理解“维护单调性”这个本质，而不是死记某一行代码。死记代码很容易在这种细节上出错。

我在实际刷题的时候发现，这类“单调队列淘汰元素”的操作和生活中的排队很像：窗口里来了一个更厉害的新人，那些无论从能力还是从排队顺序上都不可能被轮到的人，直接走人就行，留下的人都是真正有竞争力的候选者。这样一想，逻辑就好记多了。

如果后续想做更多扩展，我建议你再做一道经典题：LeetCode 239滑动窗口最大值本身，以及“和至少为K的最短子数组”这道题，它把前缀和和单调双端队列结合起来了，属于这道题的进阶版本。等你把这两道题吃透，滑动窗口这个模型在你脑子里就彻底固化了，以后再遇到类似题目基本就是秒杀。