单调队列与优先级队列：滑动窗口最大值和前K个高频元素实战解析-开发者社区

1. 专题定位与整体设计思路

1.1 为什么“栈和队列”值得单独拆两天来练

代码随想录训练营把栈和队列拆成两个专题，第一天先把栈的基本用法和经典题过一遍，第二天才开始碰队列的高级玩法。很多初学者觉得奇怪：栈和队列不就是两种“装数据”的容器吗？push、pop、top 三件套，有什么好学两天的？真正刷到 Day 11 你就会发现，第二天的内容才是这个结构真正值钱的地方——单调队列和优先级队列，前者是“窗口最大值”这类高频面试题的标准解法，后者是“前 K 个高频元素”的必考姿势。如果用错地方，或者只停留在“会调用 API”的层面，后面做滑动窗口、堆相关题目时，代码很容易写出 TLE。

我把第二天的核心理解成一句话：栈和队列不只是“容器”，它们是能维护“顺序约束”的数据结构。普通队列只能保证先进先出，单调队列能保证队内元素严格递减或递增；优先级队列则能让堆顶永远是你最关心的那个元素。弄明白这个顺序约束怎么维护、怎么失效、怎么在代码里实现，才是这专题的真正意义。

1.2 专题的目标题目与考察能力

代码随想录 Day 11 在大多数版本里，重点会落在两到三道题上：滑动窗口最大值（LeetCode 239）、前 K 个高频元素（LeetCode 347），有时还会带上一道用栈模拟队列或队列模拟栈的互用题作为热身。这几道题虽然解法差异很大，但考察的底层能力是一致的：能否把一个“线性结构”的读写顺序，变成解决具体问题的“约束条件”。

滑动窗口最大值要求窗口内 O(1) 返回最大值，这一步如果每次暴力扫一遍窗口，复杂度是 O(n×k)，数据量一上来就崩；前 K 个高频元素如果每次从哈希表里扫描找 topK，复杂度也可能是 O(n×k)。两者都是“在动态数据里快速拿极值”的场景，单调队列和堆正好各解决一个。训练营在这个时间节点放这两道题，就是希望你建立一种条件反射：看到“滑动窗口 + 最大值/最小值”，想到单调队列；看到“频率 + 前 K 个”，想到堆。

1.3 我这期专题安排与资料取舍

我的做法是先用 LeetCode 题目验证基础写法，再对照代码随想录的题解补边界细节，最后总结成一个可复用的模板。我不会把第一天的栈题重新全刷一遍，只会在队列模拟题上花 10 分钟回忆，因为第二天的核心不是“模拟”，而是“在队列里做决策”。每天的刷题计划我一般控制在 2 小时内：前半小时看题自测，中间一小时写单调队列和堆的模板，后面半小时专门用来整理边界条件。这样即使当天只有两道题，也比把题量堆到五道但每道都只写一遍要扎实得多。

2. 核心知识点拆解与实操要点

2.1 单调队列：滑动窗口最大值到底怎么做到 O(n)

先给结论：滑动窗口最大值的最优解不是用一棵平衡树，也不是每次排序，而是维护一个“队头最大”的单调递减队列。所谓单调递减，是指从队头到队尾，元素值逐渐变小；新元素入队前，把队尾所有比它小的元素全部弹出，再把它放到队尾。这样一来，队头永远是当前窗口的最大值。

为什么能弹出？因为在新元素之后，那些比新元素更小、且位置更靠前的旧元素，既不可能再是最大值，也会比新元素更早离开窗口。既然永远不会成为答案，保留它们就是纯浪费空间和时间。这个“贪心淘汰”的思想，是单调队列能在均摊 O(1) 时间内完成一次入队的根本原因。

看一段最常用的实现，我用的是存数组下标的方式：

def maxSlidingWindow(nums, k): from collections import deque dq = deque() # 存下标，不是存值 res = [] for i, x in enumerate(nums): # 1. 移除队尾比当前值小的元素 while dq and nums[dq[-1]] < x: dq.pop() # 2. 当前下标入队 dq.append(i) # 3. 移除窗口外的下标 while dq and dq[0] <= i - k: dq.popleft() # 4. 窗口形成后，队首就是最大值 if i >= k - 1: res.append(nums[dq[0]]) return res

这段代码的三个要点是：先清尾部、再入队、最后清过期头部。顺序不能乱。先入队再清头部也行，但容易把刚入队的元素误删，尤其是当新元素同时又是窗口内唯一元素时，边界条件会变得很难看。我踩过这个坑，所以建议固定这个顺序。

内层 while 虽然看起来是循环，但每个元素最多被弹出一次，因此整体均摊复杂度是 O(n)。这也是单调队列相比暴力法的最大优势：你不需要每次窗口移动都重新比较。

2.2 优先级队列：前 K 个高频元素用什么堆

前 K 个高频元素的标准思路分两步：第一步用哈希表统计每个数出现次数，得到类似 {1: 3, 2: 2, 3: 1} 的频率表；第二步用一个小顶堆维护“当前出现次数最多的 K 个数”。堆顶永远是堆中最小的那个，一旦堆中元素超过 K，就把堆顶弹出，这样堆里剩下的正好是前 K 个最大频率。

这里最容易犯错的是堆的排序方向。很多人一听“高频”就直接用大顶堆，结果把整个数组全部塞进去，再弹出 K 次，时间复杂度变成 O(n log n)，空间也浪费。正确写法是用大小为 K 的小顶堆，每次淘汰频率最小的那个，复杂度只有 O(n log K)。数据量大的时候，这个差距非常明显。

Python 里我通常这么写：

import heapq from collections import Counter def topKFrequent(nums, k): cnt = Counter(nums) return [key for key, _ in heapq.nlargest(k, cnt.items(), key=lambda x: x[1])]

如果要手动实现“小顶堆淘汰”的完整逻辑，可以这样：

def topKFrequent(nums, k): from collections import Counter import heapq cnt = Counter(nums) heap = [] for num, freq in cnt.items(): if len(heap) < k: heapq.heappush(heap, (freq, num)) else: heapq.heappush(heap, (freq, num)) heapq.heappop(heap) return [num for _, num in heap]

后一种写法在题目要求的“同频但不同数字”场景下更直观，也更容易扩展到“按字典序返回”的变体。堆里存的是二元组 (freq, num)，Python 会先按 freq 比较，再按 num 比较，所以在频率相同时可以天然保持字典序。这个特性在白板面试时非常加分。

2.3 循环队列、阻塞队列与消息队列的逻辑相通处

虽然刷题只刷抽象队列，但把视野拉宽一点，很多生产场景都建立在同样的结构上。循环队列用取模运算绕开数组搬移，典型问题就是“假设以数组 q[m] 存放循环队列中的元素，同时以 rear 和 length 分别指示环形队列中的队尾和长度，怎么判断队空队满”。答案是队空时 length == 0，队满时 length == m，入队 rear = (rear + 1) % m，出队则把 rear 往前跳 m-1 个位置，也就是 front = (rear - length + m) % m。这个题看起来和 LeetCode 无关，但它能帮你逼自己对取模边界彻底祛魅。

阻塞队列在线程池里同样常见。线程池任务队列明明看起来就是“先进先出”，但为了处理“队列满时线程该干嘛”，Java 的 ArrayBlockingQueue、LinkedBlockingQueue 引入了 put/take 的阻塞语义。队列不再只是一个存储类，而是一个“协调者”。消息队列如 Kafka、RabbitMQ、RocketMQ 更是把队列抽象成分布式组件，排序变成了分区内的顺序，重复消费变成了需要幂等处理的语义问题。刷题时能想到这些，你会更容易理解为什么“队列”这个结构在计算机系统里无处不在。

3. 实操过程与关键环节实现

3.1 从零手写单调队列模板的完整步骤

我建议第一步不要直接看题解，而是先自己写一个单调队列类。下面是标准模板，存值时用值做比较，但 LeetCode 239 推荐存下标，因为窗口过期判断更高效：

from collections import deque class MonotonicQueue: def __init__(self): self.q = deque() # 入队：把队尾所有小于 val 的元素弹出后，再追加 def push(self, val): while self.q and self.q[-1] < val: self.q.pop() self.q.append(val) # 出队：只有当队首刚好等于 val 时，才真正弹出 # 因为之前可能已经被单调性淘汰了 def pop(self, val): if self.q and self.q[0] == val: self.q.popleft() def max(self): return self.q[0]

模板的思路是，把“窗口左端要滑出的元素”交给 pop 方法处理。为什么偏偏只有当队首的值等于滑出值时才弹？因为比滑出值更小的元素，在入队阶段已经被淘汰了；而更大的元素会挡在队首，也会在未来的某个时机被滑出。这个条件判断非常精妙，也是很多新人在理解单调队列时卡住的地方。

如果你用下标版本，就不需要 pop(val) 这个方法，改为直接在循环里做“队首下标 <= i-k 就删除”。两者的效果完全一致，下标版本对窗口过期判断更直观，值版本对理解单调性更有帮助。我个人建议两种写法都至少写一遍，面试时才能根据题目要求快速切换。

3.2 前 K 个高频元素的完整流程与比较器陷阱

我用一张简单的流程表来呈现完整实操步骤：

步骤	操作	复杂度
1	遍历数组，统计每个数字出现次数	O(n)
2	遍历频率表，维护大小为 K 的小顶堆	O(n log K)
3	堆内元素转换为数组返回	O(K)

真正会卡住的往往是第 2 步的“比较器”。在 C++ 里使用 priority_queue 时，自定义比较器非常容易搞反。比如你希望堆顶是最小频率，就应该用 std::greater；希望堆顶是最大频率，就用 std::less。如果你在刷题时直接套用 Java 的 PriorityQueue 默认排序，它默认是自然序，堆顶最小，正好可以作为小顶堆使用。但是当你把比较器写反，堆顶变成最大，整个维护逻辑就会完全失效。

实操中我的习惯是，写完堆操作后立刻用一个小样例跑一遍，比如 nums = [1,1,1,2,2,3], k = 2，手动走一遍堆的变化。这一步只需要 30 秒，但能避免绝大部分比较器方向错误带来的隐藏 bug。

3.3 边界条件的三种常规处理

边界条件是这类题目能不能一次过的关键。滑动窗口最大值里最常见的是 k 比数组长度长的情况，此时窗口没有完全形成，应该直接返回空数组或者根据题目要求处理。推荐下面这个统一写法：

if k > len(nums): return [] if k == 1: return nums[:]

前 K 个高频元素里，常见边界是 k 大于不同元素的个数。这种情况下你要么返回整个频率表，要么排序后截断。代码随想录的题解一般不会特意强调这点，因为题目通常保证了 k 合法，但竞赛或面试手撕时，边界处理是重要的加分项。

另外，当窗口最大值的窗口长度刚好到达 k 时，第一次结果是在 i == k-1 时加入，而不是 i == k 时。很多新手会把 i >= k 当成判定条件，导致少算一个窗口，或者多算一次。我用一个小技巧记忆：把 k 当作索引偏移，窗口第一次完整出现的位置就是 k-1，而不是 k。

4. 常见问题与排查技巧实录

4.1 单调队列中误删队首元素

我自己的踩坑经历是这样的：用值版本单调队列时，写入 pop(val)，如果队列中存在重复的最大值，那么队首被弹出不会导致错误，但如果误把“队首等于 val”写成“队列里存在等值的元素就 pop”，队列结构会完全错乱。最常见的错误是，弹出时用了 while 循环，把窗口边界需要弹出的元素连带队列里其他相同大小的元素一起全部删除。

正确逻辑是，由于单调队列队首是当前窗口的最大值，当窗口滑出队首对应下标所代表的元素时，该元素一定在下一次 max() 调用前被移除。而如果是“队首值等于要滑出元素的值，但队首下标其实是另一个相同值”，此时不应该弹。解决方式是依赖下标比较，永不依赖值比较，除非你确定数组中没有重复值。

排查这类问题，我建议在调试器里打印 deque 和当前窗口的范围。只要能看到“队首对应的下标是否在窗口左侧之外”，基本就能定位原因。

4.2 堆比较器方向写反导致的结果错误

前 K 个高频元素最容易出现的隐蔽错误是：堆明明维护了大小，但最终结果不是降序排列。原因在于如果你用小顶堆，堆内元素是前 K 大，但弹出的顺序是从小到大，最后输出前需要逆转。如果你用大顶堆，那堆内元素不是前 K 大，而是所有元素，最后再 pop K 次得到正确答案，但复杂度变高。

我还遇到过一次类似“compare 函数返回值写反”的问题：Java 的 compare(a, b) 返回正数意味着 a 比 b 大，需要调整顺序；如果你写成“b - a”，堆顶就变成最大值。这类问题用样例 [1,1,2] 试一下就能暴露。

4.3 数组下标越界与空队列访问

很多新手在循环中直接写 dq[0]，却没先判断 deque 是否为空。单调队列有可能在窗口未形成时是空队列，或者在极端情况下队列元素全部被弹出，此时访问队首会抛异常。建议在每步操作后都加一个条件判断，但不要盲目加空判断导致代码冗余。更推荐的写法是，把“队首过期”和“取最大值”这两个动作拆开，保证取最大值时队列必然不空。

我在实盘中发现，只要严格按照“先入队、再清过期、最后取答案”的顺序，空队列访问基本不会发生。如果你看到空队列异常，多半是顺序写错了，而不是队列本身的问题。

4.4 队列模拟题中 front 与 rear 的边界问题

相关热搜词里有不少和循环队列相关的问题，比如“循环队列中同时以 rear 和 length 指示队尾和长度”的判断技巧。这里我分享一个口诀：用长度表状态，用 rear 表位置。队空不是 rear == front，而是 length == 0；队满也不是 rear == front，而是 length == 队列容量。只有把状态和位置彻底解耦，才不容易在实现时把两种判空条件混在一起。

我曾见过一个很经典的错误：入队后没有更新 length，导致队满判断失效；出队时也没有正确结算 rear，导致下一次入队覆盖了尚未读取的数据。这类 bug 用取模运算都能解决，但要求你在写代码前先在纸上画出环形数组的初始状态和三次入队出队过程。

5. 个人实际操作体会与后续展开

5.1 当日题目与后续专题的衔接方式

刷完 Day 11 后，我对“单调队列”的理解并不只是停留在解题模板，更重要的是它和后续的“单调栈”会产生对照。单调栈解决“下一个更大元素”“接雨水”等问题，单调队列解决“滑动窗口极值”问题。前者从右边着眼，后者从窗口的时效性着眼。两者都是由“某些元素永远不可能成为答案”的淘汰思想衍生出来的。把这个思想想透，后面学单调栈会顺很多。

我还发现，单调队列优化 DP 是算法竞赛里很常见的进阶方向。例如状态转移方程中出现 dp[i] = max(dp[j]) + cost，而 j 处在某个固定窗口范围内时，就可以用单调队列把 O(n^2) 优化到 O(n)。训练营里不会马上讲这个，但 Day 11 埋下的这粒种子，在遇到“最大子段和”“股票买卖变种”等题时会自动发芽。所以我建议你把单调队列模板写进自己的代码库，而不是只留在力扣编辑器里。

5.2 栈和队列在真实系统设计中的对照

刷题刷到最后，最好能跳出题目，把栈和队列带到真实系统里看。比如调用栈从 main 函数到子函数逐层压栈，栈帧形成过程其实就是函数参数、返回地址、局部变量的入栈和出栈过程。调用栈回溯则是根据栈帧里的返回地址逐层返回到调用者，这在崩溃分析和调试里非常有用。再比如线程池的阻塞队列选择：无界队列可能让任务无限堆积导致内存问题，有界队列则可能触发拒绝策略。你可以从这些角度去理解：栈是“状态恢复”，队列是“任务传递”，它们的核心价值都是控制数据流的顺序，只不过一个是后进先出，一个是先进先出。

消息队列的重复消费问题也能和队列语义联系起来。分布式队列往往无法保证完全“语义上的恰好一次”，只能通过幂等消费来解决重复消息。这和刷题时“同一个值在数组中多次出现，单调队列会不会重复处理”其实是同一个抽象问题。多想想这些类比，算法训练就不只是背题，而是真正在做工程思维的训练。