代码随想录刷题打卡来到 Day10栈与队列专题安排了三道硬菜150 逆波兰表达式求值、239 滑动窗口最大值、347 前 K 个高频元素外加一个阶段性总结。这三道题几乎把栈和队列最核心的应用场景串起来了——最近相关性用栈、窗口极值用单调队列、频率 TopK用小顶堆或桶排序。不管是准备大厂算法面试还是想扎扎实实补一遍数据结构底子这几个模式都值得反复嚼。我从大一接触栈和队列时只会背先进后出、先进先出到现在能像条件反射一样在题目里识别出该用哪种队列形态中间踩过不少坑。这篇记录我尽量把每一步都讲透包括为什么用这种数据结构、边界条件在哪里、代码为什么这么写最后再聊聊刷完这三题后对线性结构的认知升级。适合正在刷题但还没完全吃透单调队列和 TopK 思路的朋友也适合面试前需要一个快速回顾手册的人。1. 整体思路三道题背后的数据结构思维1.1 栈解决最近相关性的天然工具先聊 150 逆波兰表达式求值。很多人第一次看到逆波兰表达式会懵感觉一堆操作符和数字混在一起不知道从哪里下手。但你只要抓住一个关键点后缀表达式已经把运算符优先级和括号全部消掉了每个运算符真正需要的两个操作数就是它左侧最近的两个数。这种最近相关性正是栈最擅长的场景。栈的本质是后进先出它只允许操作栈顶。如果一个运算需要倒序处理历史数据或者只需要关心最近几个状态那用栈就不用考虑中间那些已经被处理完的元素。逆波兰求值时遇到数字就压栈遇到运算符就弹出最近的两个数字算完再压回去。这个过程等价于把表达式从左到右扫描一遍栈中始终保存着当前还没有被消费的中间结果。顺带一提热词里总能看到栈帧形成过程backtrace 栈回溯ARM 调用栈回溯这些概念。函数调用栈其实就是栈在系统层的真实写照每次函数调用会压入一个栈帧函数返回时弹出栈帧所以栈帧的空间和局部变量数量密切相关。C 语言里常说局部变量越少所占栈空间越小本质就是因为局部变量放在当前栈帧中栈帧的大小直接受局部变量影响。理解了这个场景再看算法题里的stack.pop()你会更有画面感。1.2 队列的变形金刚单调队列与优先队列239 滑动窗口最大值考的是队列但它不是直接用普通队列。普通队列解决的是先进先出的公平缓冲问题而滑动窗口需要的是随时知道窗口内最大元素以及过期元素能被及时移除。这里用到了双端队列deque并在其基础上维护单调性也就是常说的单调队列。单调队列的队首始终是窗口的最大值队尾负责淘汰那些永远不会再成为最大值的旧元素。它和普通队列最大的区别是普通队列只从队首出队、队尾入队单调队列允许在队尾直接把不合格的元素顶掉。同样出现在这组题里的 347 前 K 个高频元素则需要优先队列堆。优先队列的逻辑是每次出队的是优先级最高或最低的元素对应到 TopK 问题小顶堆记住当前最大的 K 个值堆顶就是这 K 个里最小的那个新来一个更大的就替换掉堆顶。你看同样是队列但根据需求衍生出了完全不同的形态单调队列、优先队列生产环境里还有阻塞队列、延迟队列、消息队列。理解这些变体的本质比单纯背 API 有用得多。1.3 三题背后的复杂度对比这三道题放在一起刚好构成了一组清晰的复杂度进化路线暴力能做但不是最优换对数据结构复杂度能降一个量级。我先把结论放在表格里算法题暴力思路最优方案时间复杂度150 逆波兰求值从头递归解析栈一次扫描O(n)239 滑动窗口最大值每个窗口内部求 max单调队列O(n)347 前 K 个高频元素统计频率后全排序小顶堆 / 桶排序O(n log k) / O(n)这组对比特别直观想办法让每个元素入一次、出一次而不是被反复处理往往就能得到线性复杂度。逆波兰求值里的每个数字最多入栈一次、出栈一次单调队列里的每个下标最多入队一次、出队一次桶排序里的每个元素也最多放入和取出一次。做题时养成分析每个元素被访问了几次的习惯很多看似复杂的题目就能找到优化方向。2. 150 逆波兰表达式求值栈的经典应用2.1 题目解析与数据流模拟LeetCode 150 给出的输入形如[2,1,,3,*]表示后缀表达式(2 1) * 3要求返回 9。再比如[4,13,5,/,]表示4 (13 / 5)结果是 6。解题思路就是一个栈模拟。我习惯把规则拆成三步遇到数字直接压栈。遇到运算符从栈中弹出两个数注意先弹出的是右操作数后弹出的是左操作数。按照运算符计算结果把结果压回栈中。拿[2,1,,3,*]走一遍先入栈 2再入栈 1遇到弹出 1 和 2计算 2 1 3压回 3遇到数字 3 压栈栈里是 [3, 3]遇到*弹出右操作数 3 和左操作数 3计算 3 * 3 9压回 9。扫描结束栈顶元素就是答案。整个过程非常机械但它背后藏着一个重要思想后缀表达式不存在歧义因为每个运算符的优先级已经通过位置表达清楚了。你不用像中缀表达式那样去维护两个栈一个操作数栈、一个运算符栈来处理括号和优先级。这也是为什么很多计算器在内部转换时会用到逆波兰表达式。2.2 代码实现我写了 Python 版本这是最贴近思路的写法def evalRPN(tokens: List[str]) - int: stack [] for token in tokens: if token in {, -, *, /}: b stack.pop() a stack.pop() if token : res a b elif token -: res a - b elif token *: res a * b else: # / res int(a / b) stack.append(res) else: stack.append(int(token)) return stack[0]运算符出现时为什么要弹两个数因为要严格区分a - b和b - a。后缀表达式中运算符左侧的操作数先入栈右侧的操作数后入栈所以弹出顺序一定是先右后左。如果搞反了[4,13,5,/,]会算成5 / 13而不是13 / 5结果直接错。2.3 易错点除法与负数取整的坑这道题最大的坑不是栈操作而是除法。题目要求用整数除法且结果向零截断。在 C/Java 中-3 / 2的结果是-1向零取整但在 Python 中-3 // 2的结果是-2向负无穷取整。如果直接写a // b遇到负数运算就会和预期不符。解决办法是先把除法转成浮点再用int()截断向零取整int(a / b)。这一步很关键我第一次刷的时候就是漏了它提交后有一组负数用例挂了。另一个值得注意的点是tokens里的元素全是字符串数字可能是-2这样的负数也可能是多位数12。写int(token)时不需要额外判断符号Python 的int()完全支持。2.4 面试可以说的扩展方向逆波兰表达式求值在真实工程中也有对应场景。编译原理中后缀表达式的计算就是要借助栈完成一些脚本引擎在解析用户输入时也会先把中缀表达式转成后缀再通过类似逻辑求值。面试官要是让你手写一个计算器你不用把整个转换步骤写得特别复杂先把中缀转后缀的思路说清楚再给出上面的求值过程基本就能过关。3. 239 滑动窗口最大值单调队列的威力3.1 暴力解与为什么不能用普通优先队列239 题目很经典给定数组nums有一个大小为k的滑动窗口从数组最左端移动到最右端每次移动一位要求输出每个窗口内的最大值。最直观的暴力解法是固定窗口起点遍历窗口内k个元素求最大值时间复杂度 O(n*k)在n和k都很大时直接超时。优化目标很明确能不能让每个元素只被处理常数次整体做到 O(n)有人说用优先队列最大堆啊堆顶就是最大值。这个思路方向对但有一个现实问题窗口会移动堆顶元素可能已经不在窗口内需要把它删掉。可是普通的堆只支持删除堆顶不支持快速删除某个任意元素。虽然可以延迟删除也就是用一个哈希表维护无效元素的计数等无效元素到堆顶时再弹出但实现起来代码量和管理复杂度都不小。单调队列的优势在于它利用双端队列在 O(1) 时间内从队尾弹出无用元素从队头弹出过期元素天然适配窗口滑动这个场景。每个元素最多入队一次、出队一次总复杂度 O(n)。面试时如果时间有限直接写单调队列是最稳妥的选择。3.2 单调队列维护规则画图理解单调队列到底在维护什么一句话队列中存储的是数组下标且这些下标对应的值从左到右严格递减。队首下标对应的值就是当前窗口的最大值。拿示例nums [1,3,-1,-3,5,3,6,7]k 3演示初始 i0队列空加入 0。队列[0]。i1值为3弹出队尾下标0因为 nums[0]1 3加入1。队列[1]。i2值为-1不弹出加入2。队列[1,2]。窗口满队首1对应值3输出3。i3值为-3不弹出加入3。队列[1,2,3]。输出队首3。i4值为5先将队首过期元素弹出此时窗口左边界为2队首1 2弹出1。然后弹出队尾所有 5 的下标即 2、3 都弹出再加入4。队列[4]输出5。后续依次得到 5,6,7。规则提炼成四步若队首下标已经滑出窗口即队首 当前窗口左边界弹出队首。从队尾弹出所有值小于等于当前元素值的下标。为什么小于等于也弹因为如果当前元素更大旧元素在窗口内永远不会成为最大值如果相等保留更靠后的下标也更有优势更晚过期。将当前下标压入队尾。如果当前索引已经达到k-1说明窗口已经完整滑入此时队首下标对应的值就是窗口最大值。这里有个细节步骤 1 和步骤 2 的顺序可以调整吗可以但推荐先处理过期元素再维护单调性。因为如果先加入新元素再处理过期元素可能会把刚加入的下标也误判为过期需要多写逻辑。按先过期、后单调、再入队的顺序边界好记很多。3.3 代码实现Python 使用collections.deque代码很短from collections import deque def maxSlidingWindow(nums: List[int], k: int) - List[int]: dq deque() ans [] for i in range(len(nums)): # 1. 弹出不在窗口内的队首 if dq and dq[0] i - k 1: dq.popleft() # 2. 弹出所有 当前值的队尾元素 while dq and nums[dq[-1]] nums[i]: dq.pop() # 3. 加入当前下标 dq.append(i) # 4. 窗口满后记录最大值 if i k - 1: ans.append(nums[dq[0]]) return ans这里判断过期的条件是dq[0] i - k 1其中i - k 1就是当前窗口的左边界下标。比如 i4k3左边界为 2下标 1 已经滑出窗口所以弹出。如果写成就错了会把左边界本身也弹出导致当左边界正好是最大值时出错。3.4 容易踩的坑第一个坑是用列表 List 替代 deque。Python 的list.pop(0)是 O(n) 操作在 n 很大时会让整体复杂度假性回到 O(n²)。面试时手写代码可能不在意库函数但真在 OJ 上跑性能差距非常明显。第二个坑是下标和值分不清。单调队列里存的是下标不是值。不熟练时很容易写dq存值然后发现无法判断过期只能判断最大值不知道它在窗口里的位置。所有与窗口边界有关的检查都依赖下标因此请把下标入队刻进脑子。第三个坑是单调条件使用还是。我建议用即弹出所有队尾值小于等于当前值的下标。这样做能保证相等的元素只保留最新的一个从而减少无用元素的堆积。如果你用队列里可能会同时存在多个相等的最大值虽然队首最大值依然正确但队列长度会更长清理过期元素时可能要多循环几轮。实际测试用更稳健。第四个坑是不模拟只背代码。单调队列比普通栈题抽象必须自己拿笔画一遍队列变化。我每次教朋友这道题都会要求他们手动写出[4,2,0,3,2,5]的队列快照写完全部边界就懂了。4. 347 前 K 个高频元素从频率统计到 TopK4.1 第一步哈希表统计频率题目要求返回数组中出现频率最高的前 K 个元素。比如nums [1,1,1,2,2,3]k 2返回[1,2]。第一步没有悬念用哈希表统计每个元素的出现次数。Python 直接collections.Counter或者手动dict。这一步时间复杂度 O(n)空间复杂度 O(n)。统计完成后问题变成有 m 个不同的元素每个元素带一个权重频率需要找出权重最大的前 K 个。4.2 TopK 方案的取舍为什么选小顶堆而不是大顶堆拿到频率后最简单的方法是按频率从大到小排序取前 K 个时间复杂度 O(m log m)。但很多场景下 m 很大K 很小排序显得浪费。标准解法是维护一个小顶堆堆的大小保持在 K堆顶存放这 K 个元素中频率最小的那个。每当遍历一个元素如果它的频率大于堆顶频率就弹出堆顶放入这个新元素。遍历结束后堆里剩下的就是前 K 高频。为什么必须用小顶堆而不是大顶堆因为堆大小固定为 K 时我们需要知道当前 K 个候选里谁最弱从而决定新元素是否值得替换。小顶堆的堆顶正好是当前最弱的那个比较方便如果用大顶堆堆顶是最强的你根本不知道该淘汰谁也就无法维护前 K 大。补充一下堆元素存储形式是(频率, 元素值)。如果只存频率而不存元素值最后没法还原数字Python 的 heapq 会先比较元组第一个元素频率相同再比较元素值这没问题。4.3 小顶堆实现import heapq from collections import Counter def topKFrequent(nums: List[int], k: int) - List[int]: freq Counter(nums) heap [] for num, cnt in freq.items(): heapq.heappush(heap, (cnt, num)) if len(heap) k: heapq.heappop(heap) return [item[1] for item in heap]这段代码有两个注意点。第一heapq默认是小顶堆直接能用不需要像 C 那样priority_queueint, vectorint, greaterint但如果面试要求用 Java就得在 PriorityQueue 构造函数里传比较器让频率小的优先。第二当len(heap) k才弹出可以避免多弹掉本应保留的元素判断放在 push 之后更简洁题目保证 k 小于等于不同元素个数不会出现堆空的情况。如果你希望返回结果按频率从高到低排序可以在返回前对heap做一次sorted或直接倒序输出。LeetCode 对本题的返回顺序没有硬性要求所以怎么返回都对。4.4 桶排序把 O(n log k) 优化到 O(n)追求极致的同学可以写桶排序。思路是频率的范围是 1 到 n所以我们创建n 1个桶下标表示频率桶里放对应频率的元素。统计完成后从高频率桶向低频率桶遍历把元素加入到结果中直到取满 K 个。def topKFrequent(nums: List[int], k: int) - List[int]: freq Counter(nums) buckets [[] for _ in range(len(nums) 1)] for num, cnt in freq.items(): buckets[cnt].append(num) res [] for i in range(len(buckets) - 1, 0, -1): for num in buckets[i]: res.append(num) if len(res) k: return res这个写法时间复杂度 O(n)因为桶的数量是 n1遍历一次完事且不需要排序。面试时如果你能先讲堆方案、再补充桶排序优化会显得你基本功很扎实。4.5 相关扩展堆和队列在生产环境中的影子我注意到这组热词里大量出现消息队列选型、线程池阻塞队列选择、Kafka/RabbitMQ/RocketMQ 对比等内容。其实这些生产组件离不了队列这个基础形态先进先出、缓冲削峰、生产者消费者模型。堆也广泛用于任务调度中的优先级队列、定时器的延迟队列。算法题里的单调队列、优先队列正是理解这些工程组件的最小原子单位。当然生产环境的消息队列远比算法里的队列复杂得多还涉及分布式一致性、数据持久化、重复消费等。刷完这道题再去读 Kafka 或 RocketMQ 的文档你对队列的理解会多一层直观感受它们不过是把基础数据结构延伸到了分布式系统里。这也是我一直觉得数据结构基础题值得反复刷的原因——它们永远不会过时。5. 总结栈与队列专题的实战套路5.1 从三道题提炼出的解题模板刷完整组题我给自己总结了一张数据结构速查表遇到什么特征优先考虑的数据结构参考题最近相关性 / 匹配问题 / 递归回溯栈150、20 有效括号、1047 删除字符串相邻重复项固定窗口或滑动窗口内的最值单调队列双端队列239需要维护 TopK / 动态最值堆优先队列347、215 数组第 K 大先进先出、层序扩展、生产消费普通队列 / 阻塞队列102 层序遍历、生产者消费者模型这个表不是死教条而是用特征触发的方式帮自己快速定位。做题前先用 30 秒问自己题目有没有最近有没有窗口有没有第 K 大答案基本就出来了。5.2 刷完后的认知升级数据结构不是死板的容器栈和队列学到最后你会意识到它们不只是容器更是一种约束。栈约束你只能从顶部操作所以它天然适合保存待办但最晚处理的事情队列约束你只能从一端进、另一端出所以它适合体现公平和秩序。单调队列和优先队列则是在约束之上增加排序或淘汰规则本质上是通过删除那些永远不可能成为答案的元素来降低复杂度。这种思维特别像日常生活中的排队普通队伍是先进先出VIP 通道可能插队优先级队列而滑动窗口最大值更像是一排队伍里你只需要记住目前最厉害的那个人是谁当他离开时你要知道下一个是谁。把抽象的算法还原成具体场景代码就不会写得迷迷糊糊。5.3 面试与实战小贴士最后分享几个实战建议第一优先队列可以大胆用。面试官一般不会要求你手写堆直接用heapq或priority_queue即可但你要能解释为什么 O(n log k)以及小顶堆与大顶堆的区别。第二单调队列必须能手写。因为它依赖双端队列的底层操作很多面试官会要求你实现完整的维护过程。第三拿到题先问约束n 有多大k 有多大内存限制多少这些条件直接影响方案选择比如 n 极大且不能全量加载时可能要用分布式计数而不是直接Counter。我个人刷这三题刷了差不多三轮每轮都有新理解。第一轮只会背模板第二轮搞清楚单调队列为什么能保证队首最大第三轮才真正体会到过期剔除单调性维护是一对组合拳。如果让我给一个最有价值的技巧那就是滑动窗口的题一定要画图。把窗口位置和队列状态一行一行画出来画到三次以上边界条件就永远忘不掉了。栈和队列看起来简单把它们的变化画出来比盲目刷十道题都有用。
栈与队列实战：逆波兰求值、滑动窗口最大值与前K高频
代码随想录刷题打卡来到 Day10栈与队列专题安排了三道硬菜150 逆波兰表达式求值、239 滑动窗口最大值、347 前 K 个高频元素外加一个阶段性总结。这三道题几乎把栈和队列最核心的应用场景串起来了——最近相关性用栈、窗口极值用单调队列、频率 TopK用小顶堆或桶排序。不管是准备大厂算法面试还是想扎扎实实补一遍数据结构底子这几个模式都值得反复嚼。我从大一接触栈和队列时只会背先进后出、先进先出到现在能像条件反射一样在题目里识别出该用哪种队列形态中间踩过不少坑。这篇记录我尽量把每一步都讲透包括为什么用这种数据结构、边界条件在哪里、代码为什么这么写最后再聊聊刷完这三题后对线性结构的认知升级。适合正在刷题但还没完全吃透单调队列和 TopK 思路的朋友也适合面试前需要一个快速回顾手册的人。1. 整体思路三道题背后的数据结构思维1.1 栈解决最近相关性的天然工具先聊 150 逆波兰表达式求值。很多人第一次看到逆波兰表达式会懵感觉一堆操作符和数字混在一起不知道从哪里下手。但你只要抓住一个关键点后缀表达式已经把运算符优先级和括号全部消掉了每个运算符真正需要的两个操作数就是它左侧最近的两个数。这种最近相关性正是栈最擅长的场景。栈的本质是后进先出它只允许操作栈顶。如果一个运算需要倒序处理历史数据或者只需要关心最近几个状态那用栈就不用考虑中间那些已经被处理完的元素。逆波兰求值时遇到数字就压栈遇到运算符就弹出最近的两个数字算完再压回去。这个过程等价于把表达式从左到右扫描一遍栈中始终保存着当前还没有被消费的中间结果。顺带一提热词里总能看到栈帧形成过程backtrace 栈回溯ARM 调用栈回溯这些概念。函数调用栈其实就是栈在系统层的真实写照每次函数调用会压入一个栈帧函数返回时弹出栈帧所以栈帧的空间和局部变量数量密切相关。C 语言里常说局部变量越少所占栈空间越小本质就是因为局部变量放在当前栈帧中栈帧的大小直接受局部变量影响。理解了这个场景再看算法题里的stack.pop()你会更有画面感。1.2 队列的变形金刚单调队列与优先队列239 滑动窗口最大值考的是队列但它不是直接用普通队列。普通队列解决的是先进先出的公平缓冲问题而滑动窗口需要的是随时知道窗口内最大元素以及过期元素能被及时移除。这里用到了双端队列deque并在其基础上维护单调性也就是常说的单调队列。单调队列的队首始终是窗口的最大值队尾负责淘汰那些永远不会再成为最大值的旧元素。它和普通队列最大的区别是普通队列只从队首出队、队尾入队单调队列允许在队尾直接把不合格的元素顶掉。同样出现在这组题里的 347 前 K 个高频元素则需要优先队列堆。优先队列的逻辑是每次出队的是优先级最高或最低的元素对应到 TopK 问题小顶堆记住当前最大的 K 个值堆顶就是这 K 个里最小的那个新来一个更大的就替换掉堆顶。你看同样是队列但根据需求衍生出了完全不同的形态单调队列、优先队列生产环境里还有阻塞队列、延迟队列、消息队列。理解这些变体的本质比单纯背 API 有用得多。1.3 三题背后的复杂度对比这三道题放在一起刚好构成了一组清晰的复杂度进化路线暴力能做但不是最优换对数据结构复杂度能降一个量级。我先把结论放在表格里算法题暴力思路最优方案时间复杂度150 逆波兰求值从头递归解析栈一次扫描O(n)239 滑动窗口最大值每个窗口内部求 max单调队列O(n)347 前 K 个高频元素统计频率后全排序小顶堆 / 桶排序O(n log k) / O(n)这组对比特别直观想办法让每个元素入一次、出一次而不是被反复处理往往就能得到线性复杂度。逆波兰求值里的每个数字最多入栈一次、出栈一次单调队列里的每个下标最多入队一次、出队一次桶排序里的每个元素也最多放入和取出一次。做题时养成分析每个元素被访问了几次的习惯很多看似复杂的题目就能找到优化方向。2. 150 逆波兰表达式求值栈的经典应用2.1 题目解析与数据流模拟LeetCode 150 给出的输入形如[2,1,,3,*]表示后缀表达式(2 1) * 3要求返回 9。再比如[4,13,5,/,]表示4 (13 / 5)结果是 6。解题思路就是一个栈模拟。我习惯把规则拆成三步遇到数字直接压栈。遇到运算符从栈中弹出两个数注意先弹出的是右操作数后弹出的是左操作数。按照运算符计算结果把结果压回栈中。拿[2,1,,3,*]走一遍先入栈 2再入栈 1遇到弹出 1 和 2计算 2 1 3压回 3遇到数字 3 压栈栈里是 [3, 3]遇到*弹出右操作数 3 和左操作数 3计算 3 * 3 9压回 9。扫描结束栈顶元素就是答案。整个过程非常机械但它背后藏着一个重要思想后缀表达式不存在歧义因为每个运算符的优先级已经通过位置表达清楚了。你不用像中缀表达式那样去维护两个栈一个操作数栈、一个运算符栈来处理括号和优先级。这也是为什么很多计算器在内部转换时会用到逆波兰表达式。2.2 代码实现我写了 Python 版本这是最贴近思路的写法def evalRPN(tokens: List[str]) - int: stack [] for token in tokens: if token in {, -, *, /}: b stack.pop() a stack.pop() if token : res a b elif token -: res a - b elif token *: res a * b else: # / res int(a / b) stack.append(res) else: stack.append(int(token)) return stack[0]运算符出现时为什么要弹两个数因为要严格区分a - b和b - a。后缀表达式中运算符左侧的操作数先入栈右侧的操作数后入栈所以弹出顺序一定是先右后左。如果搞反了[4,13,5,/,]会算成5 / 13而不是13 / 5结果直接错。2.3 易错点除法与负数取整的坑这道题最大的坑不是栈操作而是除法。题目要求用整数除法且结果向零截断。在 C/Java 中-3 / 2的结果是-1向零取整但在 Python 中-3 // 2的结果是-2向负无穷取整。如果直接写a // b遇到负数运算就会和预期不符。解决办法是先把除法转成浮点再用int()截断向零取整int(a / b)。这一步很关键我第一次刷的时候就是漏了它提交后有一组负数用例挂了。另一个值得注意的点是tokens里的元素全是字符串数字可能是-2这样的负数也可能是多位数12。写int(token)时不需要额外判断符号Python 的int()完全支持。2.4 面试可以说的扩展方向逆波兰表达式求值在真实工程中也有对应场景。编译原理中后缀表达式的计算就是要借助栈完成一些脚本引擎在解析用户输入时也会先把中缀表达式转成后缀再通过类似逻辑求值。面试官要是让你手写一个计算器你不用把整个转换步骤写得特别复杂先把中缀转后缀的思路说清楚再给出上面的求值过程基本就能过关。3. 239 滑动窗口最大值单调队列的威力3.1 暴力解与为什么不能用普通优先队列239 题目很经典给定数组nums有一个大小为k的滑动窗口从数组最左端移动到最右端每次移动一位要求输出每个窗口内的最大值。最直观的暴力解法是固定窗口起点遍历窗口内k个元素求最大值时间复杂度 O(n*k)在n和k都很大时直接超时。优化目标很明确能不能让每个元素只被处理常数次整体做到 O(n)有人说用优先队列最大堆啊堆顶就是最大值。这个思路方向对但有一个现实问题窗口会移动堆顶元素可能已经不在窗口内需要把它删掉。可是普通的堆只支持删除堆顶不支持快速删除某个任意元素。虽然可以延迟删除也就是用一个哈希表维护无效元素的计数等无效元素到堆顶时再弹出但实现起来代码量和管理复杂度都不小。单调队列的优势在于它利用双端队列在 O(1) 时间内从队尾弹出无用元素从队头弹出过期元素天然适配窗口滑动这个场景。每个元素最多入队一次、出队一次总复杂度 O(n)。面试时如果时间有限直接写单调队列是最稳妥的选择。3.2 单调队列维护规则画图理解单调队列到底在维护什么一句话队列中存储的是数组下标且这些下标对应的值从左到右严格递减。队首下标对应的值就是当前窗口的最大值。拿示例nums [1,3,-1,-3,5,3,6,7]k 3演示初始 i0队列空加入 0。队列[0]。i1值为3弹出队尾下标0因为 nums[0]1 3加入1。队列[1]。i2值为-1不弹出加入2。队列[1,2]。窗口满队首1对应值3输出3。i3值为-3不弹出加入3。队列[1,2,3]。输出队首3。i4值为5先将队首过期元素弹出此时窗口左边界为2队首1 2弹出1。然后弹出队尾所有 5 的下标即 2、3 都弹出再加入4。队列[4]输出5。后续依次得到 5,6,7。规则提炼成四步若队首下标已经滑出窗口即队首 当前窗口左边界弹出队首。从队尾弹出所有值小于等于当前元素值的下标。为什么小于等于也弹因为如果当前元素更大旧元素在窗口内永远不会成为最大值如果相等保留更靠后的下标也更有优势更晚过期。将当前下标压入队尾。如果当前索引已经达到k-1说明窗口已经完整滑入此时队首下标对应的值就是窗口最大值。这里有个细节步骤 1 和步骤 2 的顺序可以调整吗可以但推荐先处理过期元素再维护单调性。因为如果先加入新元素再处理过期元素可能会把刚加入的下标也误判为过期需要多写逻辑。按先过期、后单调、再入队的顺序边界好记很多。3.3 代码实现Python 使用collections.deque代码很短from collections import deque def maxSlidingWindow(nums: List[int], k: int) - List[int]: dq deque() ans [] for i in range(len(nums)): # 1. 弹出不在窗口内的队首 if dq and dq[0] i - k 1: dq.popleft() # 2. 弹出所有 当前值的队尾元素 while dq and nums[dq[-1]] nums[i]: dq.pop() # 3. 加入当前下标 dq.append(i) # 4. 窗口满后记录最大值 if i k - 1: ans.append(nums[dq[0]]) return ans这里判断过期的条件是dq[0] i - k 1其中i - k 1就是当前窗口的左边界下标。比如 i4k3左边界为 2下标 1 已经滑出窗口所以弹出。如果写成就错了会把左边界本身也弹出导致当左边界正好是最大值时出错。3.4 容易踩的坑第一个坑是用列表 List 替代 deque。Python 的list.pop(0)是 O(n) 操作在 n 很大时会让整体复杂度假性回到 O(n²)。面试时手写代码可能不在意库函数但真在 OJ 上跑性能差距非常明显。第二个坑是下标和值分不清。单调队列里存的是下标不是值。不熟练时很容易写dq存值然后发现无法判断过期只能判断最大值不知道它在窗口里的位置。所有与窗口边界有关的检查都依赖下标因此请把下标入队刻进脑子。第三个坑是单调条件使用还是。我建议用即弹出所有队尾值小于等于当前值的下标。这样做能保证相等的元素只保留最新的一个从而减少无用元素的堆积。如果你用队列里可能会同时存在多个相等的最大值虽然队首最大值依然正确但队列长度会更长清理过期元素时可能要多循环几轮。实际测试用更稳健。第四个坑是不模拟只背代码。单调队列比普通栈题抽象必须自己拿笔画一遍队列变化。我每次教朋友这道题都会要求他们手动写出[4,2,0,3,2,5]的队列快照写完全部边界就懂了。4. 347 前 K 个高频元素从频率统计到 TopK4.1 第一步哈希表统计频率题目要求返回数组中出现频率最高的前 K 个元素。比如nums [1,1,1,2,2,3]k 2返回[1,2]。第一步没有悬念用哈希表统计每个元素的出现次数。Python 直接collections.Counter或者手动dict。这一步时间复杂度 O(n)空间复杂度 O(n)。统计完成后问题变成有 m 个不同的元素每个元素带一个权重频率需要找出权重最大的前 K 个。4.2 TopK 方案的取舍为什么选小顶堆而不是大顶堆拿到频率后最简单的方法是按频率从大到小排序取前 K 个时间复杂度 O(m log m)。但很多场景下 m 很大K 很小排序显得浪费。标准解法是维护一个小顶堆堆的大小保持在 K堆顶存放这 K 个元素中频率最小的那个。每当遍历一个元素如果它的频率大于堆顶频率就弹出堆顶放入这个新元素。遍历结束后堆里剩下的就是前 K 高频。为什么必须用小顶堆而不是大顶堆因为堆大小固定为 K 时我们需要知道当前 K 个候选里谁最弱从而决定新元素是否值得替换。小顶堆的堆顶正好是当前最弱的那个比较方便如果用大顶堆堆顶是最强的你根本不知道该淘汰谁也就无法维护前 K 大。补充一下堆元素存储形式是(频率, 元素值)。如果只存频率而不存元素值最后没法还原数字Python 的 heapq 会先比较元组第一个元素频率相同再比较元素值这没问题。4.3 小顶堆实现import heapq from collections import Counter def topKFrequent(nums: List[int], k: int) - List[int]: freq Counter(nums) heap [] for num, cnt in freq.items(): heapq.heappush(heap, (cnt, num)) if len(heap) k: heapq.heappop(heap) return [item[1] for item in heap]这段代码有两个注意点。第一heapq默认是小顶堆直接能用不需要像 C 那样priority_queueint, vectorint, greaterint但如果面试要求用 Java就得在 PriorityQueue 构造函数里传比较器让频率小的优先。第二当len(heap) k才弹出可以避免多弹掉本应保留的元素判断放在 push 之后更简洁题目保证 k 小于等于不同元素个数不会出现堆空的情况。如果你希望返回结果按频率从高到低排序可以在返回前对heap做一次sorted或直接倒序输出。LeetCode 对本题的返回顺序没有硬性要求所以怎么返回都对。4.4 桶排序把 O(n log k) 优化到 O(n)追求极致的同学可以写桶排序。思路是频率的范围是 1 到 n所以我们创建n 1个桶下标表示频率桶里放对应频率的元素。统计完成后从高频率桶向低频率桶遍历把元素加入到结果中直到取满 K 个。def topKFrequent(nums: List[int], k: int) - List[int]: freq Counter(nums) buckets [[] for _ in range(len(nums) 1)] for num, cnt in freq.items(): buckets[cnt].append(num) res [] for i in range(len(buckets) - 1, 0, -1): for num in buckets[i]: res.append(num) if len(res) k: return res这个写法时间复杂度 O(n)因为桶的数量是 n1遍历一次完事且不需要排序。面试时如果你能先讲堆方案、再补充桶排序优化会显得你基本功很扎实。4.5 相关扩展堆和队列在生产环境中的影子我注意到这组热词里大量出现消息队列选型、线程池阻塞队列选择、Kafka/RabbitMQ/RocketMQ 对比等内容。其实这些生产组件离不了队列这个基础形态先进先出、缓冲削峰、生产者消费者模型。堆也广泛用于任务调度中的优先级队列、定时器的延迟队列。算法题里的单调队列、优先队列正是理解这些工程组件的最小原子单位。当然生产环境的消息队列远比算法里的队列复杂得多还涉及分布式一致性、数据持久化、重复消费等。刷完这道题再去读 Kafka 或 RocketMQ 的文档你对队列的理解会多一层直观感受它们不过是把基础数据结构延伸到了分布式系统里。这也是我一直觉得数据结构基础题值得反复刷的原因——它们永远不会过时。5. 总结栈与队列专题的实战套路5.1 从三道题提炼出的解题模板刷完整组题我给自己总结了一张数据结构速查表遇到什么特征优先考虑的数据结构参考题最近相关性 / 匹配问题 / 递归回溯栈150、20 有效括号、1047 删除字符串相邻重复项固定窗口或滑动窗口内的最值单调队列双端队列239需要维护 TopK / 动态最值堆优先队列347、215 数组第 K 大先进先出、层序扩展、生产消费普通队列 / 阻塞队列102 层序遍历、生产者消费者模型这个表不是死教条而是用特征触发的方式帮自己快速定位。做题前先用 30 秒问自己题目有没有最近有没有窗口有没有第 K 大答案基本就出来了。5.2 刷完后的认知升级数据结构不是死板的容器栈和队列学到最后你会意识到它们不只是容器更是一种约束。栈约束你只能从顶部操作所以它天然适合保存待办但最晚处理的事情队列约束你只能从一端进、另一端出所以它适合体现公平和秩序。单调队列和优先队列则是在约束之上增加排序或淘汰规则本质上是通过删除那些永远不可能成为答案的元素来降低复杂度。这种思维特别像日常生活中的排队普通队伍是先进先出VIP 通道可能插队优先级队列而滑动窗口最大值更像是一排队伍里你只需要记住目前最厉害的那个人是谁当他离开时你要知道下一个是谁。把抽象的算法还原成具体场景代码就不会写得迷迷糊糊。5.3 面试与实战小贴士最后分享几个实战建议第一优先队列可以大胆用。面试官一般不会要求你手写堆直接用heapq或priority_queue即可但你要能解释为什么 O(n log k)以及小顶堆与大顶堆的区别。第二单调队列必须能手写。因为它依赖双端队列的底层操作很多面试官会要求你实现完整的维护过程。第三拿到题先问约束n 有多大k 有多大内存限制多少这些条件直接影响方案选择比如 n 极大且不能全量加载时可能要用分布式计数而不是直接Counter。我个人刷这三题刷了差不多三轮每轮都有新理解。第一轮只会背模板第二轮搞清楚单调队列为什么能保证队首最大第三轮才真正体会到过期剔除单调性维护是一对组合拳。如果让我给一个最有价值的技巧那就是滑动窗口的题一定要画图。把窗口位置和队列状态一行一行画出来画到三次以上边界条件就永远忘不掉了。栈和队列看起来简单把它们的变化画出来比盲目刷十道题都有用。
