企业官网建设流程全解析

滑动窗口最大值这题，很多人第一次碰到是在LeetCode 239上，看起来就是个“滑动窗口里找最大”的数组题，实际上背后藏着单调队列这种非常经典的数据结构思想。面试里它几乎是必考题，而且面试官往往会追问各种变形：为什么暴力解过不了？堆为什么不是最优？单调队列到底在维护什么？如果只是背过答案，很容易在追问环节露馅。这篇文章我把这道题从原理到代码彻底拆开，从暴力解法的缺陷讲起，到双端队列维护单调性、再到各种边界坑点，最后把滑动窗口最小值、中位数、硬件滤波这类延伸场景一并串起来，希望读完你不仅能AC这道题，还能理解它背后的通用套路。

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……最后一共输出 n - k + 1 个最大值，也就是 8 - 3 + 1 = 6 个结果：[3,3,5,5,6,7]。

这个题表面上是“求数组区间最大值”，但它有个特殊约束：窗口是固定长度的，而且每次只移动一步。这个约束决定了我们不能简单地把每个窗口当作独立区间处理，因为相邻窗口之间有大量重叠——如果能利用这种重叠关系，就能避免重复计算。

我见过不少初学者第一反应是排序，把每个窗口里的k个数排个序取最大。这个思路在数据量小的时候没错，但一旦k接近n，比如数组长度10万、窗口大小5万，排序的总代价会高到无法接受。问题的关键在于：滑动窗口是一种流式过程，我们要的不是单次查询，而是连续、实时地维护一个动态集合的极值。

1.2 暴力解法为什么不行

最直观的解法就是枚举所有窗口，对每个窗口从头到尾扫一遍找最大值。外层循环有 n - k + 1 个窗口，每个窗口内部扫描 k 个元素，总时间复杂度是 O(nk)。

当 n 和 k 都取到 10^5 级别时，n乘以k就是10^10次操作，在常规OJ上基本是超时级别的。就算 k 比较小，这个写法也谈不上优雅。更关键的是，暴力解法完全没有利用窗口移动的重叠信息——窗口向右移一格，只是丢掉最左边一个元素、加入最右边一个新元素，其余 k - 1 个元素根本没有任何变化，但我们还是把整个窗口重新扫了一遍，这是在反复做无用功。

还有一种常见思路是用大顶堆（优先队列），把当前窗口的元素全部塞进堆里，堆顶就是最大值。窗口移动时删除离开的元素、添加新元素，然后取堆顶。这个方向比暴力好不少，时间复杂度是 O(n log k)。不过它可以继续优化，因为堆的删除操作往往需要“延迟删除”，而且堆里维护了所有窗口元素，但我们真正需要的只是“当前窗口里的最大值”，大量非最大元素其实根本没必要保留。

如果面试时你回答“用优先队列”，面试官大概率会追问一句：“能不能做到O(n)？” 这时候就是单调队列登场的时候了。

1.3 窗口移动时发生了什么

为了设计高效解法，需要非常具体地描述窗口移动的每一步操作。假设窗口右边界已经到下标 i，窗口覆盖范围是 [i - k + 1, i]。窗口向右移动一位后，右边界变成 i + 1，覆盖范围变成 [i - k + 2, i + 1]。

对比移动前后的窗口，只有一个元素离开（下标 i - k + 1）和一个元素加入（下标 i + 1）。所以理想情况下，每次移动我们只需要处理“一个出队”和“一个入队”，然后想办法快速知道新的最大值。

问题转化成：维护一个动态数据集合，支持在集合头部删除一个元素、在集合尾部插入一个元素，并且能快速返回集合中的最大值。

数组的随机访问、链表的头尾插入删除都很快，但“快速求最大值”这个需求，需要额外设计。单调队列就是为这个场景量身定做的：它本质上是一个双端队列，但通过维护队列内元素的单调性，让队首永远保存当前窗口的最大值。

2. 单调队列：这道题的标准答案

2.1 为什么偏偏是双端队列

双端队列（Deque）允许从队首和队尾两端进行插入和删除。滑动窗口移动时，过期元素从窗口左端离开，新元素从窗口右端进入，天然对应了双端队列的头部删除和尾部插入。

但仅仅支持两端的插入删除还不够，我们还需要快速拿到最大值。如果队列元素是无序的，找最大值还得遍历，那就白折腾了。所以核心思路是：让队列里的元素保持某种单调性——比如从队首到队尾单调递减。这样队首就是最大值，每次取答案只要 O(1)。

维持单调性的办法也很巧妙：当新元素要入队时，不断从队尾弹出所有比新元素小的元素（以及后面会讨论的等于的情况），直到队尾元素比新元素大，或者队列为空，然后把新元素从队尾入队。

为什么可以放心弹出队尾那些较小的元素？因为这些被弹出的元素下标都比新元素小（它们是先来的），而值又比新元素小或者相等。在滑动窗口的视角下，新元素“又大又新”，意味着只要新元素还在窗口里，那些旧的小元素就永远不可能是窗口最大值。既然它们已经对答案没有贡献，留着只会增加队列长度，不如直接弹掉。这一手就是单调队列的精髓——用“下标更大、值也更大”的元素去淘汰不可能成为答案的“前辈”。

2.2 队列里到底存下标还是存值

很多第一次写单调队列的人会下意识把元素值本身存进队列，这其实埋了个大坑：当窗口移动、需要判断队首元素是否已经滑出窗口时，光有值根本无法判断它是什么时候进来的，也就无法判断它是否过期。

正确的做法是队列里存数组下标，比较大小的时候用 nums[下标] 去取值。这样做了两件事：一是可以通过下标判断元素是否在窗口范围内；二是取最大值答案时可以直接用 nums[队首下标]，不需要额外存储。

这里顺便说一下队列单调性的方向。我们要维护的是“最大值”，所以队列里的元素值从队首到队尾应该是递减的，队首最大。如果题目改成求滑动窗口最小值，就把单调性反过来，队列里元素值从队首到队尾递增，队首最小。整个算法框架不变，变的只是比较符号和弹出条件。

2.3 完整手推一个例子

用 nums = [1,3,-1,-3,5,3,6,7] 和 k = 3 来手动走一遍流程，你会彻底理解每个步骤的意义。

队列 q 初始为空。

• i = 0，nums[0] = 1：队列空，直接把下标0入队。q = [0]。
• i = 1，nums[1] = 3：队尾下标0对应的值是1，3 > 1，所以弹出下标0，然后把下标1入队。q = [1]。
• i = 2，nums[2] = -1：队尾下标1对应的值是3，-1 < 3，不弹出，直接把下标2入队。q = [1, 2]。此时窗口 [0,2] 已经形成，队首下标1对应的值是3，记录结果 3。
• i = 3，nums[3] = -3：队尾下标2对应的值是-1，-3 < -1，不弹出，入队下标3。q = [1, 2, 3]。先检查队首下标1是否过期：窗口左边界是 i - k + 1 = 1，下标1没有过期，队首值3，记录结果3。
• i = 4，nums[4] = 5：队尾下标3对应的值是-3，5 > -3弹出下标3；队尾下标2对应的值是-1，5 > -1弹出下标2；队尾下标1对应的值是3，5 > 3弹出下标1；队列空，入队下标4。q = [4]。窗口左边界是 2，下标4自然没过期，队首值5，记录5。
• i = 5，nums[5] = 3：队尾下标4对应的值是5，3 < 5，不弹出，入队下标5。q = [4, 5]。窗口左边界是3，队首下标4没过期，队首值5，记录5。
• i = 6，nums[6] = 6：队尾下标5对应的值是3，6 > 3弹出下标5；队尾下标4对应的值是5，6 > 5弹出下标4；队列空，入队下标6。q = [6]。窗口左边界是4，下标6没过期，队首值6，记录6。
• i = 7，nums[7] = 7：队尾下标6对应的值是6，7 > 6弹出下标6，入队下标7。q = [7]。队首值7，记录7。

最终结果 [3,3,5,5,6,7]，和题目要求的输出完全一致。整个过程每个元素最多入队一次、出队一次，均摊下来每次操作就是 O(1)，总复杂度 O(n)。

注意到这个过程中有一个重要细节：比如 i=3 的时候，窗口其实已经包含了下标1、2、3三个元素，队列里也是 [1,2,3]，三个元素都在窗口内，没有冗余。而 i=4 的时候，窗口是 [2,3,4]，但队列里只剩 [4] 了，因为下标2、3对应的 -1、-3 都被 5 淘汰掉了——它们确实不可能成为当前或未来窗口的最大值，因为 5 比它们大而且比它们晚过期。

2.4 为什么这道题不能用线段树、ST表这类RMQ结构

看到这里可能有朋友会问：区间最大值不是还可以用线段树、ST表、稀疏表之类的RMQ结构吗？确实可以，但它们在滑动窗口场景下都不是最优解。

ST表可以做到 O(1) 查询任意区间最大值，但预处理是 O(n log n) 的。滑动窗口是一个在线过程，窗口每次移动都要查一次，如果用 ST表，总复杂度 O(n log n + n)，多了个 log 不太划算。线段树支持单点更新和区间查询，也可以 O(log n) 地维护窗口，但同样带 log。

单调队列之所以是这道题的“标准答案”，就是因为滑动窗口有一个其他场景没有的特性：窗口左边界和右边界都在同方向单调移动。这个特性让我们可以只用一个双端队列，在线性时间内完成全部任务。如果题目变成“数组不变、任意询问区间最大值”，那才需要用 ST表或者线段树；如果变成“数组动态修改、询问区间最大值”，那线段树和树状数组这类结构才是合适的。不同的动态性，对应不同的数据结构，这是算法题里特别重要的一种思考方式。

3. 三种主流语言实现与代码细节

3.1 Java 版本：基于 ArrayDeque

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<>(); int idx = 0; for (int i = 0; i < n; i++) { // 1. 清理过期下标：当前窗口左边界为 i - k + 1 while (!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[idx++] = nums[deque.peekFirst()]; } } return res; } }

这段代码有几个地方值得停下来细说。

第一，清理过期下标的时机。我习惯在“入队新元素之前”先清理队首过期元素，这样保证队列里所有元素都是当前窗口的有效元素。也看到过有人后清理，先入队再检查过期，那样做其实也能AC，但逻辑上没那么干净，容易在连续弹出的时候判断出错。

第二，维护单调性时用的是<=而不是<。也就是说，当队尾元素值和新元素相等时，我也会把队尾弹出去。这个细节很多人不理解，我单独解释一下。两个相等值的元素，新来的那个下标更大，在滑动窗口里它存活的时间更久。既然值一样大，旧元素能做的贡献新元素全部能做，且新元素更晚离开窗口，所以旧的相等元素对后续任何窗口都没有价值，直接淘汰。如果用<保留相等元素，队列里会残留“值相同但下标更小”的元素，它们虽然不影响当前窗口的最大值结果，但会让队列长度更长，在极端情况下（比如数组中有大量连续重复值），队列可能退化成 O(k) 的长度，虽然复杂度依然是均摊 O(1)，但没必要多占空间。

第三，记录答案的条件i >= k - 1。窗口从下标0开始覆盖，但真正形成完整窗口需要右边界到达 k - 1。在这之前，窗口不足k个元素，队首虽然存在，但它代表的窗口并不完整，不能作为答案。很多新手容易在这里栽跟头，把前 k - 1 个不完整窗口的结果也输出了。

第四，关于 ArrayDeque 的容量问题。Java 的 ArrayDeque 会自动扩容，所以不需要手动管理大小。有人担心它不能存 null，这里我们存的全是 int 下标，没有 null 问题，放心用。

3.2 C++ 版本：基于 deque

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); vector<int> res; deque<int> dq; for (int i = 0; i < n; ++i) { while (!dq.empty() && dq.front() < i - k + 1) { dq.pop_front(); } while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); if (i >= k - 1) { res.push_back(nums[dq.front()]); } } return res; } };

C++ 的 deque 头文件是<deque>，pop_front()和pop_back()分别对应头部和尾部弹出。这里有一个常见的坑：很多人用queue而不是deque，但queue只支持队首弹出、队尾插入，无法从队尾弹出，而我们的算法必须从队尾“淘汰”元素，所以queue是做不到的。deque才是正确的容器选择。

另外，C++ 中如果对nums[dq.back()]和nums[i]的比较不小心把<=写成了<，在后续的答案正确性上一般不会出错，但队列里会留着多余的相等元素，调试的时候队列状态看起来会比较“脏”。我建议统一写成<=，思路最清晰。

3.3 Python 版本：基于 collections.deque

from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) if n == 0 or k == 0: return [] q = deque() res = [] for i in range(n): # 弹出过期下标 while q and q[0] < i - k + 1: q.popleft() # 维护单调递减 while q and nums[q[-1]] <= nums[i]: q.pop() q.append(i) if i >= k - 1: res.append(nums[q[0]]) return res

Python 的deque支持下标访问q[0]、q[-1]，使用起来最直观。要注意popleft()和pop()的区别：前者从左边弹出，对应过期元素清理；后者从右边弹出，对应维护单调性时的尾部淘汰。这两个方法名字容易搞混，写的时候别把popleft()写成pop()，否则行为完全不对。

Python 还有一个优点：deque可以在两端 O(1) 地插入删除，底层是双向链表加块状数组的结构，性能足够。如果你把队列换成普通 list，q.pop(0)是 O(n) 的，一旦 n 大了就会超时。

3.4 复杂度到底是多少

每个下标最多入队一次、出队一次，入队出队都是 O(1)，所以整个算法的时间复杂度是 O(n)。虽然代码里有两个 while 循环嵌套在 for 循环里，但均摊分析下总操作次数不会超过 2n，完全符合线性复杂度。

空间复杂度是 O(k)，因为队列里最多同时存在 k 个下标（在极端情况下比如数组严格递减且没有过期元素时，队列确实会装满 k 个元素）。但在大多数情况下，由于单调性维护会淘汰大量元素，队列实际长度通常远小于 k。

这个 O(n) 的复杂度，比堆的 O(n log k) 整整下降了一个数量级。这也是为什么面试官在听到“优先队列”之后会追问“能不能优化”——单调队列就是这道题的最优解之一。

4. 实战中的五个高频坑与排查心得

4.1 队列存值而不是存下标

这是我见过最多的初级错误。有人觉得既然队列里维护的是“候选最大值”，那直接把值存进去不就行了？问题在于“过期判断”必须依赖下标。窗口移动一步后，左边界变成 i - k + 1，你需要知道队首元素的下标是否小于这个边界。如果队列里只有值，你根本无从判断这个值到底属于哪个位置。

举个例子：窗口大小 k = 3，当前窗口覆盖 [2,3,4] 下标，队列中可能存了一个很大的值 99，但它是下标2的元素。下一次窗口变成 [3,4,5]，下标2已经过期了。如果队列里只有 99 而没有下标，你怎么知道它该不该被弹出？没法知道。所以严格来说：队列里必须存下标，比较大小用 nums 做索引取值。

4.2 while 和 if 的区别：为什么要循环弹出

维护单调性的时候，很多人会写成一个if而不是while。这样写的问题在于：队尾可能不止一个元素比新元素小，如果只弹一个，那队列仍然不满足单调递减，后续的“队首即最大值”性质就被破坏了。

比如队列现在是 [5, 3, 2]，新元素是 4。如果只弹一个（把2弹掉），队列变成 [5, 3, 4]，队尾 4 前面还有一个 3，但它比 4 小。这样队列从队首到队尾是 5, 3, 4，并不是单调递减的，虽然队首还是5不影响当前窗口的答案，但下一次新元素再来的时候，这个不单调的队列会让“淘汰逻辑”出错——比如新元素是 6，它会连续弹出4、3，然后发现队首5也被淘汰，队列清空，最终结果还是对的，但万一新元素是 4.5，它把4弹掉，队列变成 [5,3]，看似没毛病，但那个3明明比4.5小，却被留在了队里，它会在之后干扰判断。

所以这里必须用while，直到队尾元素大于当前值或者队列为空才停。这个细节，我在面试别人的时候也经常看到，属于“背代码没理解原理”的典型案例。

4.3 过期清理和单调性维护的先后顺序

两种顺序都能得到正确答案，但我强烈建议先清理过期元素，再插入新元素。原因是逻辑更清晰：第一步确保队列中元素全在窗口内，第二步处理单调性时才不会受到过期元素的干扰。

如果你先入队新元素，再清理过期元素，可能会遇到一个隐藏问题：新元素比队尾所有元素都大，把队列清空后又入队，此时队首是新元素本身，它当然不是过期元素，清理队首的循环条件对它不生效，结果是对的。但假如新元素的值相当小，它被直接追加到队尾，紧接着清理过期元素的循环开始从队首弹，这也不会有问题。所以两种顺序都能AC，但先清理过期的写法更不容易在面试的紧张氛围里写错，建议养成这个习惯。

4.4 等于号的处理：用 <= 还是 <

前面已经提过，我推荐在弹出队尾时使用<=。这里再展开解释一下利弊。

假设数组是 [2, 1, 2]，k = 2。如果弹出条件用<而不是<=，过程是这样的：

• i = 0，队列空，入队0，q = [0]。
• i = 1，队尾0对应值1（即 nums[0]=2）与 nums[1]=1 比较，2 > 1，不弹，入队1。q = [0,1]。窗口完整，队首值2，记录2。
• i = 2，队尾1对应值1，nums[2]=2，弹出条件如果是<，2 > 1 不成立，不弹。然后检查过期：左边界 i-k+1 = 1，队首0过期，弹出0；q = [1]。再入队2，q = [1,2]。队首值是 nums[1]=1，记录1。但实际窗口是 [1,2]，最大值应该是2。答案错误！

看到了吗？这里问题不是出在等于号，而是出在“旧的大元素已经过期”后，没有及时用新元素淘汰掉那个值为1的元素。如果弹出条件用<=，i=2 时就会先弹出队尾的1，再把2入队，队首变成2，答案就对了。

从这个例子可以看出来，在边界情况下，用<会导致队列中残留“值相等但下标更小”的元素，一旦“更大的旧元素”过期，这个残留的小值就可能顶上来充当最大值，造成错误。所以务必使用<=。

4.5 窗口未完整时没有延迟记录答案

最后这个坑在初学者里非常普遍：在第一层循环里，前 k - 1 个元素进来时，窗口长度不足 k，但有同学会直接从 i = 0 开始记录队首作为答案，导致答案数组前面多出来好几个“伪最大值”。

比如 nums = [4, 1, 2, 3]，k = 3。如果从 i = 0 就开始记录，会输出 [4, 3, 2, 3] 这样的4个值，但正确答案只需要 2 个值：[4, 3]（窗口[4,1,2]最大4，窗口[1,2,3]最大3）。所以一定要等 i >= k - 1 再开始记录结果。

5. 滑动窗口思想的工程化延伸

5.1 镜像问题：滑动窗口最小值

如果你理解了最大值版本的单调递减队列，求最小值就是一分钟的事：把队列维护成单调递增，队首就是最小值，弹出条件从“队尾值 <= 当前值”改成“队尾值 >= 当前值”，其余完全一样。

这个镜像问题在很多场景里都有用。比如股票的滚动最低价、系统日志在固定时间窗口内的最低延迟、机器学习里滑动窗口的特征归一化（需要窗口内的 min 和 max）等。其实力扣也有类似题目，比如求滑动窗口中的最小值，套上同一个模板就能秒掉。

我这里给一个通用模板的记忆方式：求最大值，队列从头到尾递减（大在前）；求最小值，队列从头到尾递增（小在前）。判断队尾该不该弹，就看新元素能不能“干掉”队尾——能干掉的标准就是队尾不再是“极值的候选者”。

5.2 滑动窗口中位数：为什么需要对顶堆

滑动窗口中位数比最值复杂一个档次。中位数不是窗口的极值，而是“中间位置”的值，无法靠单调队列直接维护，因为队列的单调性只能保证极值在两端，保证不了中间值是哪个。

常见做法是对顶堆：一个大顶堆维护窗口左半部分的元素，一个小顶堆维护右半部分的元素，两个堆的大小始终维持着某种平衡（比如大顶堆比小顶堆多1个或相等），那么大顶堆的堆顶就是中位数。窗口移动时，需要从对应的堆里删除离开的元素（通常用延迟删除），再插入新元素，然后调整两个堆的平衡。整体复杂度 O(n log k)，比求最值的 O(n) 要高，这也是为什么中位数问题不能照搬单调队列。

从热词里能看到“滑动窗口中位数”确实是一个被广泛搜索的高频痛点。如果你把239题的单调队列套路用在这里，会发现根本行不通——所以遇到新题，先想清楚问题的本质是“极值”还是“位置”，再决定数据结构。

5.3 硬件视角：滑动窗口滤波和Verilog的窗口想法

我注意到有很多搜索词是关于“滑动窗口滤波verilog”“滑动窗口滤波器延迟”的。这其实是硬件/信号处理领域里非常常见的需求：在一个固定长度的采样窗口内，计算均值、最大值、最小值等统计量，用来做信号平滑或异常检测。

软件算法里的单调队列思想，在硬件实现上通常不会直接对应。FPGA上的滑动窗口滤波通常用移位寄存器（shift register）按周期存储采样值，然后用组合逻辑并行计算窗口内所有数据的比较结果。每个时钟周期窗口滑动一次，旧数据从寄存器链末端丢出，新数据从输入端移入，最大值通过一组比较器树（comparator tree）得到。

从这个角度看，“滑动窗口最大值”并不是纯软件练习题，它在实时信号处理、传感器数据采集、金融指标计算等场景里都有影子。软件和硬件的差距在于：软件用“淘汰不可能成为答案的元素”来降低复杂度；硬件则用“并行计算所有元素”来保证每周期都输出结果。它们一个省时间，一个换吞吐，各有各的取舍。

5.4 数组区间最大值查询的兄弟们

热词里还有“n个数确定第k个最大值”“数组求区间最大值的算法题”这类搜索。它们是滑动窗口最大值题目的远房亲戚。

“n个数确定第k个最大值”是 TopK 问题。如果 k 固定且远小于 n，可以用大小为 k 的小顶堆维护“当前最大的k个元素”，堆顶就是第 k 大的数。也可以用快速选择算法（QuickSelect）在平均 O(n) 时间内求出。这和滑动窗口最大值的思路不同——TopK 没有窗口移动的约束，是静态集合的统计。

“数组求区间最大值”则是一类更宽泛的问题。如果数组是静态的、大量任意区间查询，用 ST表预处理后可以做到 O(1) 查询；如果数组支持单点修改，就需要线段树；如果只是固定长度的滑动窗口，才是单调队列的主场。选择哪种方案，完全取决于你的操作模式是“查询多”“更新多”还是“窗口固定移动”。

5.5 数据流场景与生产实践的启发

热词中出现了“kafka 读写最大值与硬件关系”这种工程向的搜索。它和本题算法没有直接联系，但指向一个更普遍的事实：流式数据场景里，我们经常需要在一段不断滑动的窗口中统计极值、均值、计数等。

生产环境里常见的监控系统，比如Prometheus的rate()函数、滑动窗口限流器（固定窗口或滑动窗口统计请求速率）、交易系统的滚动风险管理，本质上都在做类似的事情：维护一个不断向前移动的窗口，计算窗口内的某种聚合值。这时候，单调队列、前缀和、双指针这些“基础算法”，就不仅仅是面试题，而是真正能落地到线上系统的工具。

比如实现一个滑动窗口限流器：限制任意1秒内最多允许N个请求。你可以用一个队列记录每个请求的时间戳，每次新请求来时，把队列头部所有过期时间戳弹出，然后看队列长度是否超过N。这其实就是“滑动窗口内计数”的经典实现，和239题的“滑动窗口内最大值”共享同一套窗口维护思想。

5.6 这道题还能怎么变形

最后聊几个常见的变形，帮助你把单调队列这个工具打磨得更锋利。

第一个变形是“滑动窗口最大值+最小值同时输出”。做法是同时维护一个单调递减队列和一个单调递增队列，各自按规则更新。这个变形的价值在于，很多滑动窗口优化题（比如求“满足某某条件的最短子数组”）需要同时知道窗口内的max和min来调整左右指针。

第二个变形是“字符串滑动窗口”，比如“无重复字符的最长子串”。这类题目不再用双端队列维护单调性，而是用哈希表记录字符上一次出现的位置，本质上还是窗口边界的动态管理。窗口思想是共通的，但具体数据结构要因题而异。

第三个变形是“多重滑动窗口”，比如在二维矩阵里做固定大小子矩阵的最大值。这一类题通常需要两次单调队列：先在每一行做一次滑动窗口最大值，得到一个新矩阵，再在每一列对新矩阵做一次滑动窗口最大值，最终得到每个子矩阵的最大值。这个过程也被称为“二维滑动窗口最大值”，是239题的经典高阶应用。

这些变形题，我在刷题和实际面试中都遇到过。如果能把239题的底层原理吃透，这些变形题大多只是“套两层循环”和“换一下比较条件”的区别。

6. 实操总结与个人体会

我最早刷这道题的时候，也想当然地用了优先队列，然后被提示“能不能O(n)”彻底卡住。后来认真推了一遍单调队列的整个流程，尤其亲自画了几个例子（包括相等元素、极端递增递减序列）之后，才真正理解“为什么可以弹出队尾的较小元素”这件事的本质。从那之后，很多窗口类的题目我都能秒联想到底层数据结构该用什么。

据我个人的刷题经验，这套模板有几个值得反复咀嚼的要点：第一，队列里存下标是铁律，别偷懒存值；第二，弹出相等的旧元素是保证正确性的关键，别省那个等号；第三，先清理过期再入队新元素，是最好写也最好debug的顺位；第四，窗口完整才记录结果。这四点我称之为“239四诫”，每次写到类似的题我都会在心里默念一遍。

如果你正在准备面试，我建议你不仅要把代码写熟，还要能把“为什么双端队列能做到O(n)”这件事用两三句话讲清楚。面试官问这道题，往往不只是考你会不会写，还想看你能不能把他引到“单调性”“淘汰策略”“均摊分析”这些点上。你要是能主动提到“延迟无效元素”“下标生命周期”这些词，面试体验会完全不一样。

最后再分享一个调试技巧：遇到边界用例不通过，就在纸上把数组和队列的变化过程一行行列出来，对标一下每一步的队首、队尾和答案。比如用 [1,-1,1,2,-3,3] 这种含负数、含相等值、含递增递减混合的数据，跑三遍就基本能把所有隐藏bug挖出来。比对着代码瞪眼有效得多。