单调队列与优先级队列：滑动窗口最大值和前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(), keylambda 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 函数到子函数逐层压栈栈帧形成过程其实就是函数参数、返回地址、局部变量的入栈和出栈过程。调用栈回溯则是根据栈帧里的返回地址逐层返回到调用者这在崩溃分析和调试里非常有用。再比如线程池的阻塞队列选择无界队列可能让任务无限堆积导致内存问题有界队列则可能触发拒绝策略。你可以从这些角度去理解栈是“状态恢复”队列是“任务传递”它们的核心价值都是控制数据流的顺序只不过一个是后进先出一个是先进先出。消息队列的重复消费问题也能和队列语义联系起来。分布式队列往往无法保证完全“语义上的恰好一次”只能通过幂等消费来解决重复消息。这和刷题时“同一个值在数组中多次出现单调队列会不会重复处理”其实是同一个抽象问题。多想想这些类比算法训练就不只是背题而是真正在做工程思维的训练。5.3 给后来的刷题者的一些建议最后聊一点实操节奏。如果你和我一样是在职刷题每天能抽出的完整时间不超过两小时那 Day 11 的重点建议放在“单调队列 优先级队列”这两个模板上不要贪多。第一遍允许照着题解抄模板但要抄完立刻合上书用自己的语言把思路讲给旁边的玩偶或者录音笔听。讲不清楚的地方就是你还不会的地方。第二遍可以尝试把单调队列的“值版本”改成“下标版本”把前 K 个高频元素的“排序法”改成“堆法”强制自己用至少两种方式写同一道题。这个过程虽然慢但比盲目刷十道类似的题有效得多。等你能在白板上一边画窗口滑动过程一边解释为什么被弹出的元素不可能成为答案时这道题才算真正过关。