企业官网建设流程全解析

刷 LeetCode 的朋友应该都有体会，数组区间类的题目里，“滑动窗口最大值”这一题几乎绕不开。很多人在看到这道题的第一反应是：这还不简单？每次窗口移动就遍历一遍窗口找最大值，搞定。等真正提交完发现超时之后，才意识到问题的核心其实不是“怎么找最大值”，而是“如何在窗口滑动时高效地维护这个最大值”。

今天就把这道题彻底聊透。我会从最直觉的暴力解法开始，逐步拆解为什么需要“单调队列”，并给出可直接抄作业的实现代码、复杂度分析，以及我实际写题时踩过的坑。无论你是刚接触滑窗的新手，还是准备面试想快速复习，这篇文章都能让你少走不少弯路。

1. 题目本质与暴力解法的困境

1.1 题目到底在问什么

给你一个整数数组nums，有一个长度为k的滑动窗口从数组的最左侧移动到最右侧。你只能看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位，要求返回滑动窗口中的最大值。用大白话说：有一个长度固定的框，每次挪一格，每挪一次你都要报出框里最大的数。

这个场景在现实中太常见了。比如监控一组传感器数据，取最近 5 秒的最大值判断是否越界；或者统计股票价格最近 30 天的最高点。本质上都是在长度为k的窗口内反复求最大值。LeetCode 第 239 题就是把这个场景抽象成算法题。

题目链接大家很熟悉了，输入输出格式就不多啰嗦。关键在于nums的长度可能到达10^5，k也可能接近10^5，如果每个窗口都去遍历，总操作量就会是 O(nk) 级别，最坏情况下是10^10，这在现代计算机上也是不可接受的。所以这道题表面上是“求最大值”，实际上考的是“动态维护最值”的数据结构功底。

1.2 暴力法的时间成本定量分析

先给一个直观的数字。假设n = 100000，k = 50000，那么需要计算约n - k + 1 = 50001个窗口，每个窗口暴力找最大值需要比较50000次，总比较次数大约是25亿。即使每纳秒进行一次比较，也要 2.5 秒，实际情况显然更慢。LeetCode 的判题系统通常限制在 1~2 秒内，暴力解法必然超时。

还有一层容易被忽略的：暴力法不仅时间慢，代码写起来也容易引入边界错误。每次窗口滑动时，我们其实已经知道上一轮的最大值了，只是不知道窗口移出去的那个数会不会影响当前最大值。如果移出去的数字恰好是上次的最大值，那么新窗口的最大值必须重新扫描整个窗口；如果移出去的不是最大值，并且新加入的数字比当前最大值小，那最大值可以沿用。但问题是，你怎么知道移出去的那个是不是最大值？用变量记录当然可以，但一旦最大值被移出，你还是得重新扫描。所以暴力法的本质缺陷不是“笨”，而是没有充分利用窗口滑动前后的重叠信息。

2. 高效算法的核心：单调双端队列

2.1 为什么优先队列也不行

有人可能会想：用一个最大堆不就行了？把窗口里的元素都放进堆里，堆顶就是最大值。窗口滑动时，删掉滑出的元素，加入新元素，复杂度是 O(log k)。总复杂度 O(n log k)，看着能过。

但这里有个隐藏的坑：堆的删除操作并不方便。如果你只记录值本身，当窗口滑出一个元素时，你怎么知道该删除哪个？你可能会把值和下标一起存进堆，但堆顶如果是滑出窗口的旧值，你只能“延迟删除”——等它到堆顶时再判断下标是否还在窗口内。这个做法虽然可行，但代码复杂度一下子就上去了，而且处理不当还会留下很多“过期”元素在堆里，导致内存和性能的浪费。

单调队列能把这个过程优化到每个元素均摊 O(1)，而且思路非常直观。它的核心思想是：窗口内那些“既比别人小，又排在别人后面”的元素，永远没机会成为最大值，可以直接从数据结构里丢掉。这种“淘汰弱小”的机制，就是单调队列的灵魂。

2.2 单调队列的维护原理

我直接用一个具体例子说清楚。假设nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3。

我们从左到右遍历数组，用一个双端队列（deque）来存储元素下标。存储下标而不是值，是为了方便判断元素是否还在窗口内。队列中下标对应的元素值必须是从队首到队尾严格递减（或非递增）的，因此队首永远是当前窗口的最大值。

遍历到第一个元素1，队列为空，直接把下标 0 入队，此时队列为[0]，队首对应值 1 就是最大值。

遍历到第二个元素3，下标 1。首先检查队尾元素nums[0] = 1，发现1 < 3，说明1在未来的窗口里永远不可能是最大值（因为3不仅比它大，而且位置比它靠右，活得比它久），所以把队尾的下标 0 弹出。然后把下标 1 入队。此时队列为[1]，最大值 3。

遍历到第三个元素-1，下标 2。检查队尾nums[1] = 3，3 > -1，所以-1不弹出，直接入队。队列为[1, 2]，对应值[3, -1]，确实是递减的。此时窗口已经包含了前三个元素，所以第一个窗口的最大值就是队首下标 1 对应的nums[1] = 3。

遍历到第四个元素-3，下标 3。队尾是nums[2] = -1，-1 > -3，所以-3直接入队，队列为[1, 2, 3]，对应值[3, -1, -3]。但在记录结果前，需要检查队首下标 1 是否已经滑出当前窗口。当前窗口是下标 2, 3, 4（即[-1, -3, 5]？等等，这里我顺序有点跳，需要重新理一下）。

我重新来一遍，严谨起见：

数组：[1, 3, -1, -3, 5, 3, 6, 7]，窗口长度 3。

• i=0，队列：[]，入队0。队列 [0]，窗口还没满（长度1），不记录。
• i=1，nums[1]=3，队尾nums[0]=1 < 3，弹出0，入队1。队列 [1]，窗口长度2，不记录。
• i=2，nums[2]=-1，队尾nums[1]=3 > -1，入队2。队列 [1,2]，窗口长度3，窗口 [0,1,2]。检查队首1，下标1在当前窗口内，最大值 nums[1]=3，记录。
• i=3，nums[3]=-3，队尾 nums[2]=-1 > -3，入队3。队列 [1,2,3]。当前窗口是 [1,2,3]（下标1~3）。检查队首1，在窗口内，最大值 nums[1]=3，记录。注意这里虽然新元素 -3 很小，但不影响最大值。
• i=4，nums[4]=5，队尾下标3对应nums[3]=-3 < 5，弹出3；队尾下标2对应nums[2]=-1 < 5，弹出2；队尾下标1对应nums[1]=3 < 5，弹出1。队列空，入队4。窗口是 [2,3,4]，最大值 nums[4]=5，记录。
• i=5，nums[5]=3，队尾下标4对应nums[4]=5 > 3，入队5。队列 [4,5]。窗口是 [3,4,5]，队首下标4在窗口内，最大值 nums[4]=5，记录。
• i=6，nums[6]=6，队尾下标5对应nums[5]=3 < 6，弹出5；队尾下标4对应nums[4]=5 < 6，弹出4；入队6。窗口是 [4,5,6]，最大值 nums[6]=6，记录。
• i=7，nums[7]=7，队尾下标6对应nums[6]=6 < 7，弹出6；入队7。窗口是 [5,6,7]，最大值 nums[7]=7，记录。

最终结果[3,3,5,5,6,7]。完美符合预期。

这个过程里最关键的操作就两个：当新元素大于等于队尾元素时，持续弹出队尾（这里“等于”也要弹出，因为等于的时候，旧元素位置靠左，寿命更短，被新元素替代更合理）；入队后，检查队首下标是否小于当前窗口的左边界，如果是，则弹出队首。前者保证队列的单调递减性，后者保证队首元素属于当前窗口。

2.3 为什么存储下标而不是存储值

很多初学者会问：直接在队列里存数字不就完了？反正比较大小只需要值。这里有一个非常隐蔽的边界问题：当窗口滑动时，我们怎么知道队首元素是不是已经滑出去了？只存值的话，你根本不知道它在数组中的位置，也无法判断它是否还在窗口内。存下标就完美解决了这个问题：每次入队后，检查queue.front() <= i - k，如果成立，说明这个下标已经滑出窗口，直接弹出。

举一个实际场景：nums = [5, 4, 3, 2, 1]，k = 3。如果只存值，当第二个窗口[4,3,2]到来时，队列里可能还存着5，但 5 已经不在窗口内了。你只看到队首是 5，就把它当成最大值，结果就错了。存下标的话，一看 0 比i - k = 1小，马上弹掉，队首变成 1 对应的 4，结果正确。

所以“存下标”不是偏好，而是必须。

3. 代码实现与逐行精讲

3.1 Python 实现（最清晰版本）

from collections import deque from typing import List class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: if not nums or k == 0: return [] if k == 1: return nums[:] dq = deque() result = [] for i in range(len(nums)): # 1. 弹出所有比当前元素小的队尾元素 while dq and nums[dq[-1]] < nums[i]: dq.pop() # 2. 当前元素入队（存下标） dq.append(i) # 3. 弹出所有已经不在窗口内的队首元素 # 注意：这里不能用 if，因为可能队首是滑出窗口的旧下标，但队首弹出后，新队首也可能滑出？ # 实际上由于窗口长度固定，每次最多只有一个下标滑出，但由于我们可能存储了多个过期下标？ # 队列中的下标是递增的，最多只有一个下标正好等于 i - k，所以 if 就可以了。 # 但为了安全，使用 while 也没问题。 if dq[0] <= i - k: dq.popleft() # 4. 当窗口长度达到 k 时，记录结果 if i >= k - 1: result.append(nums[dq[0]]) return result

这段代码的核心只有 4 步，我再逐个拆开解释。

第 1 步的while dq and nums[dq[-1]] < nums[i]：这里的<不是<=。如果你用<=，当新元素和队尾元素相等时，你会把队尾元素弹掉。这其实是更优的选择，因为相等的旧元素寿命更短，但如果你希望保留旧元素也没问题，结果不影响。不过为了队列里元素的下标尽量靠右，通常推荐用<=把相等的也弹掉。我上面的代码用的是<，两种都行，面试时只要说清楚就行。

第 3 步的判断if dq[0] <= i - k：为什么用<=而不是<？因为当窗口右边界是i时，左边界是i - k + 1。如果队首下标等于i - k，说明它恰好是上次窗口的最后一个元素，已经不在当前窗口内，必须弹出。我第一次写的时候用了<，结果在窗口长度变化时总差一个位置，调试半天才意识到边界差 1。

第 4 步的if i >= k - 1：这个条件保证窗口形成后才开始记录。比如k = 3，前两个元素时窗口没满，不记录。从第三个元素开始，每次循环结束都会有一个窗口结果。

3.2 C++ 实现（面试常用版本）

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> res; for (int i = 0; i < nums.size(); ++i) { // 保持单调递减 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); // 移除窗口外的元素 if (dq.front() <= i - k) { dq.pop_front(); } // 记录结果 if (i >= k - 1) { res.push_back(nums[dq.front()]); } } return res; } };

C++ 版本和 Python 几乎一模一样，只是语法差异。这里while用了<=，还有刚才说的弹出策略，都是标准的写法。注意if (dq.front() <= i - k)这里的判断条件，因为i - k是窗口左边界减一，所以老手一眼能看懂为什么是<=。

3.3 常见错误：while和if的边界之争

我再强调一个特别容易栽的坑：第三步的弹出队首操作。很多新手写成while dq[0] <= i - k: dq.popleft()。从正确性角度看没问题，但从性能上看，由于每次循环最多少一个元素滑出窗口，if就够了。但如果你用if，必须确保队列里不可能存在多个滑出窗口的下标。仔细想想：队列里的下标是严格递增的，而且每次入队前我们都把小的、旧的元素弹掉了，队尾永远比队首新。所以当队首滑出窗口时，它一定是最老的那个，而且队列中下一个元素的下标肯定大于它，因此只有队首可能滑出。用if是安全的。

但如果你的队列不是单调的（因为之前用了错误的弹出条件），就可能出现多个过期下标堆在队首，这时必须用while。所以真正的根源在于维护队列的单调性和下标严格递增，而不是选择哪种写法。

3.4 复杂度为什么是 O(n)

看代码感觉里面有while循环，会不会退化？关键点在于：每个元素最多被入队一次、出队一次。虽然内层while可能一口气弹出多个元素，但那些元素在后续循环中不会再出现了，所以所有pop操作的总次数不超过n。因此总时间复杂度是 O(n)，空间复杂度是 O(k)，因为队列最多容纳窗口长度个元素。

有人较真说队列里可能存了超过 k 个元素吗？不可能。由于队首会及时弹出，加上单调性，队列长度最多等于窗口长度k。证明也简单：如果队列长度超过 k，那么队首下标必然小于等于i - k，早就被弹掉了。所以空间绝对线性。

4. 边界条件与性能优化细节

4.1 特殊输入的应对

边界条件一：k = 1。每个窗口只有一个元素，最大值就是元素本身，直接返回原数组。很多解法不写这个特判也能跑，因为算法本身会正确输出，但提前返回可以省去不必要的队列操作，也避免一些实现上的奇怪问题。如果你用我上面的代码，k=1时，dq永远只存一个元素，result的每个值就是nums[i]，正确。但为了保险和效率，特判没坏处。

边界条件二：k >= nums.length。此时窗口覆盖整个数组，最后只输出一个最大值，也就是整个数组的最大值。我的代码会自动处理，因为i从 0 到 n-1，最后i >= k-1始终成立（如果 k 大于 n，那就只有最后一次满足条件？不，如果 k 大于 n，比如 n=5, k=10，则i最大为 4，i >= 9永远不成立，结果为空数组，这是不对的。等等，题目一般规定 k <= n，但很多实现里如果 k > n，期望输出整个数组的最大值。所以我一般会加一个：如果k >= nums.size()，直接返回max_element的结果。这一点在调试时容易忽略。

边界条件三：空数组。返回空数组。这个不用多解释。

边界条件四：数组中存在重复值。刚才提到了<=和<的区别，无论哪种，结果都不会错。但要注意，如果使用<，当出现连续相等的最大值时，队首可能会保留较旧的下标，直到它被滑出窗口。这时检查dq[0] <= i - k就非常必要。如果改用<=，相等的旧元素会提前被弹掉，队首下标更靠右，逻辑更顺滑。

4.2 一个被忽略的性能细节：减少模块调用

用 Python 刷题时，deque的popleft是 O(1)，但如果你用普通的list加pop(0)，那就是 O(k) 的复杂度，整体会退化成 O(nk)。很多没接触过双端队列的新手会踩这个坑。所以在 Python 里必须from collections import deque。同理，Java 里用ArrayDeque，C++ 里用deque。不要图省事用Queue，因为Queue是接口，实现类可能底层是链表，插入删除也 O(1)，但一般无需用线程安全的BlockingQueue。

还有一个细节：result预约空间。Java 和 C++ 可以提前res.reserve(n - k + 1)或vector<int> res(n - k + 1)，避免多次扩容。Python 的列表动态扩容虽然效率还行，但如果要极致，也可以用preallocate但没必要。

4.3 单调队列 vs 分块/稀疏表

既然聊到性能，顺便对比一下其他能解决这个问题的数据结构。分块法可以把复杂度做成 O(n√n)，稀疏表可以 O(1) 查询每个窗口，但预处理 O(n log n)。单调队列的优势是线性时间且代码短。不过如果你需要在线处理连续不断到来的数据，且窗口长度不固定，单调队列的调整方式会更灵活。而稀疏表适合窗口大小随机查询多次的场景。这个对比在面试时如果被追问，能展示你对数据结构的整体认知。

5. 题目变体与扩展思路

5.1 窗口最小值怎么办

镜像一下就行。把单调队列改成单调递增，队首就是最小值。判断条件从nums[dq[-1]] < nums[i]改成>，其他完全一样。很多人觉得这是新题，其实一行之差。我建议你在本地把最大值版本的代码复制一份，改一下比较符号，跑一遍测试用例，很快就能掌握。

5.2 滑动窗口中位数怎么求

热词里有人提到“滑动窗口中位数”，这也是经典题。用两个堆（大顶堆 + 小顶堆）或者有序容器，常数内可以获取中位数，但复杂度是 O(log k)。如果要求 O(n) 就得用某种平衡树或者双堆维护，无法用单一单调队列解决，因为中位数需要中间位置的数据，单调队列只能维护极值。这里容易区分类比：如果题目只问最大值、最小值，用单调队列；如果问中位数、第 k 大，用堆或平衡树。

我最近看到有人拿滑动窗口最大值的思想去做“信号滤波”，比如取最近 N 个采样点的最大值作为滤波输出，用来剔除突变干扰，这在 Verilog 数字信号处理里也有对应的硬件实现，核心思路类似：边滑边维护极值，不过硬件上用的是寄存器阵列比大小。算法原理是相通的。

5.3 单调队列思想的通用模板

其实可以总结一个通用模板，适用于所有“固定窗口滑动 + 求某种单调可维护信息”的题目：

• 初始化空双端队列
• 遍历每个元素：
  1. 维护单调性（弹出队尾所有不再有竞争力的元素）
  2. 入队
  3. 删除队首超出窗口的元素
  4. 如果窗口已满，记录答案

唯一变化的只有第 1 步的比较逻辑和答案选取方式。把这个模板背熟，再理解每一步在做什么，比死记代码强多了。

6. 实战中的调试技巧与心得

6.1 自己写测试用例的方式

很多人在 LeetCode 上错了就在那盯着代码发呆。我建议你准备一套小用例，手动跑。比如nums = [1, -1]，k = 1，输出是[1, -1]；nums = [1]，k = 1，输出是[1]；nums = [1, -1]，k = 2，输出是[1]。这几个简单的用例能快速暴露边界条件的错误。另外一定要用下降序列和上升序列分别测试，因为滑动窗口最大值最容易在单调序列上暴露队首过期和处理不及时的问题。

6.2 在代码里打印队列状态的技巧

调试单调队列时，打印队列里的下标和值非常有用。你可以在每次循环结束后打印d的内容和当前窗口边界。比如：

print(f"i={i}, dq_idx={list(dq)}, dq_val={[nums[idx] for idx in dq]}, window=[{max(0, i-k+1)}..{i}]")

这样就能直观看到每一步的维护过程，也能发现“为什么队首值不对”之类的问题。等代码正确以后，再把这些打印删掉。

6.3 面试时怎么讲思路

如果你在面试中遇到这题，不要上来就写代码。先和面试官确认：数组长度多大？窗口长度是否固定？返回值是每次窗口的最大值对吧？然后从暴力解法切入，分析时间复杂度，引出单调队列。讲解时用一个具体例子走一遍维护过程，强调为什么存储下标是关键。最后再写代码。这样整个流程非常自然，也体现了你的思维过程。

7. 踩坑记录与个人经验

7.1 我犯过的三个典型错误

第一次写这道题时，我在第三步用了if但把边界条件写成了dq[0] < i - k，导致当队首恰好等于i - k时没弹掉，结果错误的把上一个窗口的最大值带入了当前窗口。其实应该是<=，因为下标等于i - k的元素已经在窗口左边界之外了。

第二次是入队前忘了清空所有小的元素，只清了一个，导致队列不是单调的。比如nums = [2, 1, 5]，窗口大小 2，当我处理到 5 时，队列里如果还存着 1，那 5 后面还有 2，1 在 2 后面但比 2 小，如果不弹干净，队列会变成[1, 2, 5]不是单调递减，队首就不是最大值了。必须用while把所有比当前元素小的都弹掉。

第三次是在k = 0时没有处理，直接报错。LeetCode 里一般不会给k = 0，但如果你写通用工具函数，必须考虑。

7.2 如何记忆这道题的方法论

我觉得最核心的一句话就是：“如果一个元素比它在窗口里后面的元素还小，那它永远不可能成为这个窗口的最大值，赶紧丢。” 这就是单调性的本质。面试时如果能说出这句话，基本就能证明你理解了。剩下的代码只是把这句话翻译成while循环和deque操作。

7.3 写在最后的小建议

滑动窗口最大值这道题，强烈建议你至少自己手写三遍以上。第一遍看着题解写，第二遍关掉题解自己推，第三遍尝试在不看代码的前提下，只是用大白话描述步骤，然后凭这个描述写出代码。第三遍如果能做到，你在面试中遇到它的任何变体都不会慌。另外，别只刷这道题，试着把“滑动窗口最小值”“滑动窗口极值差”都写一遍，一通百通。

我在实际刷题过程中还有一个体会：单调队列不是专门为这道题发明的，它是一个很通用的思想。很多看似无关的问题，比如“求每个长度为 k 的子段最大差值”“求连续子数组的某种极值”，本质上都能用这个思路去优化。把这道题吃透，收益远不止一道题。