今天刷到《代码随想录》Day10的三道题做完之后反而有种“原来栈与队列不是我以为的那样”的感觉。150逆波兰表达式求值、239滑动窗口最大值、347前K个高频元素这三道题放在同一天并不是因为都用了栈或队列而是因为它们在逼你重新理解“数据结构”这三个字——它不是一个装着固定API的容器而是你面对不同场景时简化问题的思维方式。如果你也在跟着代码随想录刷题或者刚学到栈与队列这一章希望这篇记录能帮你把这三道题的底层逻辑串起来。我会把每一步的推导过程、代码细节、踩过的坑、以及面试里可能追问的变形都展开聊一聊保证不是简单的题解复述而是真正能带走的东西。1. 为什么这三道题会排在同一天栈与队列的真实分工1.1 数据结构不是死记的API而是场景的答案很多人在学栈和队列时记的都是“栈是先进后出队列是先进先出”然后到了做题的时候看到“括号匹配”就条件反射用栈看到“层序遍历”就用队列。但一旦题目换个包装比如逆波兰表达式、滑动窗口、出现频率TopK就立刻卡住了。其实这三道题正好对应了三种典型需求逆波兰表达式求值需要的是“保存最近的操作数遇到运算符就取出来算算完再放回去”。这种最近优先、后到先处理的操作顺序恰好是栈的天然属性。滑动窗口最大值需要的是“窗口向右移动时快速淘汰已经滑出窗口的数据并且随时知道当前窗口的最大值”。这种带时效性和顺序性的数据维护最适合用队列——但需要给它加上“单调”的约束。前K个高频元素需要的是“从一堆元素中快速挑出出现频率最高的K个”。这已经不是先进先出或后进先出的问题而是“优先级”的问题所以要引入优先级队列也就是堆。如果你把这三题放在一起看会发现它们分别展示了栈、队列、优先级队列各自最擅长处理的场景。数据结构不是一套死板的东西它是你在描述数据流动方式时用最合适的结构去模拟这种流动。1.2 三题同做的节奏感从“会写代码”到“会选结构”我实际把三道题做完的感触是150题是保底题只要想通“运算符是动作”就能过239题是分水岭如果没用过单调队列第一次基本会被卡住347题则是前三章知识的一次汇总哈希表、排序思想、堆全部揉在一起。代码随想录把这顺序排成“150 - 239 - 347”我个人觉得是循序渐进的设计先让你用一次栈的完整入栈出栈过程建立“操作顺序”的感觉再用单调队列告诉你队列里的元素不是只能被动排队你完全可以制定规则让不满足条件的元素提前出队最后到347直接让你从上一步的“队列”跳出来进入“堆”的世界明白TopK问题其实不需要维护全部数据的有序性。这个节奏本身就是一种方法论训练先掌握最朴素的数据结构再给它加规则最后再换成更高效的数据结构去解决问题。2. 150 逆波兰表达式求值把运算符看作动作而不是符号2.1 逆波兰表达式为什么能让计算机轻松求解逆波兰表达式也叫后缀表达式它的特点就是运算符写在操作数后面比如“3 4”写成了“3 4 ”。我们人类平时用的中缀表达式里有括号、有优先级计算机要处理的话还得先转成后缀表达式或者用递归的思路去解析。但后缀表达式本身是没括号、没歧义的你只需要从左往右扫描遇到数字就压栈遇到运算符就弹出两个数计算再把结果压回栈。这个逻辑我第一次看到的时候觉得太简单了甚至有点怀疑这也能算一道LeetCode的150题但实际写起来才发现真正的坑不在算法流程而在边界条件和运算细节上。具体流程可以拆成这么几步遍历tokens数组中的每个元素。如果当前元素是数字直接转换成整数然后push进栈。如果当前元素是运算符、-、*、/从栈中弹出两个数先弹出的记为right后弹出的记为left。用left和right执行对应运算把结果push回栈。遍历结束后栈中唯一剩下的元素就是表达式的结果。这里最需要注意的一句话是先弹出的是右操作数后弹出的是左操作数。因为栈是LIFO后进先出你遇到的运算符时最近的两个数字在栈顶但压栈顺序是左操作数先压、右操作数后压所以弹出顺序恰好反过来。如果不加区分直接拿第一个弹出的数当左操作数加减乘除里只有加和乘这种对称运算不出问题但减法和除法一定出错。2.2 整数除法与负数的截断问题我在Python里第一次写的时候顺手写了这样的逻辑right stack.pop() left stack.pop() if token : stack.append(left right) elif token -: stack.append(left - right) elif token *: stack.append(left * right) else: stack.append(left / right) # 这里有问题跑用例的时候遇到除法就错了。因为LeetCode 150的题目要求是只保留整数部分也就是向零截断truncate toward zero。但Python的/返回的是浮点数比如6 / 4会得到1.5这不符合题目要求用//也不行因为//是向下取整对于正数没问题但遇到负数时结果不同。举个例子-7 // 2在Python里结果是-4因为它是向负无穷方向取整而题目要求的是向零截断正确结果应该是-3。处理办法有两种把结果转成int(float(left) / float(right))这样会把-7 / 2 -3.5转成-3因为int()在截断时是向零取整的。用math.trunc()或者自定义一个整数除法函数让除法的结果在正负情况下都向零取整int(left / right)。在C里也有类似的坑C的整数除法本身就是向零截断的所以用C刷这题不需要额外处理负数的情况但Python必须显式截断。这就是“用Python刷题”和“用C刷题”的差异点之一。我当时最后提交的版本是这样的from typing import List class Solution: def evalRPN(self, tokens: List[str]) - int: stack [] for token in tokens: if token in -*/: right stack.pop() left stack.pop() if token : stack.append(left right) elif token -: stack.append(left - right) elif token *: stack.append(left * right) else: stack.append(int(left / right)) else: stack.append(int(token)) return stack[0]注意if token in -*/这里其实有个小问题如果token是一个多位数比如12它不会出现在-*/里所以没问题。但如果token是负数比如-5它也不在-*/里依然走int(token)的逻辑所以没问题。可如果某个token恰好是/或者-这样的单个符号就只能走运算符分支。这种做法虽然可行但严谨一点应该用集合if token in {, -, *, /}:因为in加字符串在语义上等价于子串判断如果你的操作数里包含两个字符比如的变体是不可能的但能明确一下总是好的。2.3 逆波兰表达式题目最容易踩的三个坑第一个坑用list做栈的时候只关心append和pop不关心栈为空的情况。正常的表达式不会让你在只有一个操作数时遇到运算符所以不用判空。但如果题目改成了“表达式可能存在错误”就需要加上栈长度的检查。LeetCode 150没有这个要求所以不用画蛇添足。第二个坑除法结果的符号问题。上面已经说过Python里用int(left / right)是安全的但如果你用int(left // right)在负数场景下会出错。刷题的时候千万记得先跑一遍带负数的用例比如[10, 6, -, 5, /]手动算一下是(10-6)/5 4/5 0用//也算0但换成负数就暴露了。第三个坑不要试图用递归或中缀转后缀来做。题目直接给了后缀表达式你只需要完成“求值”这一半如果你用中缀转后缀再去求值等于做了一遍两步转换不仅代码更复杂效率也低了。认清题目边界也是一种刷题能力。我个人觉得150题是典型的“思路简单代码细节容易出错”的题目。它考察的是你对栈操作顺序的敏感度以及在整数运算边界上的处理经验。越是看起来简单的题越要养成“写出自测用例”的习惯。3. 239 滑动窗口最大值暴力法的天花板和单调队列的剪枝逻辑3.1 为什么暴力法会超时数据规模下的必然这道题最直接的思路是枚举所有长度为k的窗口每个窗口都遍历一遍找最大值。nums的长度是n窗口个数是n - k 1每个窗口扫描k个元素总时间复杂度是O(n * k)。当n和k都达到10^5量级时这个复杂度是10^10量级显然是超时的。我第一次拿到题目时还心存侥幸有没有可能Python暴力也能过实测不行LeetCode后面有一组特别大的数据会直接把你卡住。所以必须想更快的做法。暴力法慢在哪儿慢在每个窗口都要重新找最大值而相邻窗口只会增加一个元素、减少一个元素大量信息是可以复用的。如果你能设计一个数据结构让每次窗口滑动都能以O(1)或O(log n)的代价拿到当前最大值问题就解决了。这里自然想到队列窗口从左往右移动每次移出窗口的元素在左边新进入窗口的元素在右边。用队列模拟这个“先进先出”的过程刚好符合窗口的滑动方向。所以问题就变成了能不能维护一个队列队列头部始终保持当前窗口的最大值3.2 单调队列的核心思想淘汰掉永远不可能成为最大值的元素单调队列顾名思义是队列里的元素值保持单调这里是单调递减。队列头部是最大值尾部是最小值。每次新元素入队时从尾部开始把所有比当前元素小的旧元素全部弹出因为它们比当前元素更小、而且在窗口里的位置更靠左意味着它们会先滑出窗口它们再也不可能成为窗口最大值了。这个“淘汰”逻辑是整个思路的灵魂。你可以这样理解排队时你前面的人都比你矮而且比你年纪大那么他们一定会比你先离开窗口。既然他们又矮又先走在窗口里永远轮不到他们当最大值所以直接让他们从队伍里消失。留下的人要么比你高要么比你年轻在窗口里待得更久。除了值的大小每个元素还有自己的“过期时间”。所以队列里不能只存值还要存下标。每次窗口滑动时先检查队首元素的下标是否已经滑出窗口如果滑出了就把它弹出。然后再执行上述的单调性维护。这样就保证队首永远是“当前窗口内最大的元素”。3.3 手写单调队列的完整代码与细节我常用的是用collections.deque来实现因为它两端都能以O(1)复杂度进行操作。如果用Python的list在头部pop会涉及到元素移动复杂度不是严格O(1)。写代码的时候可以自己封装一个MonotonicQueue类也可以直接在一个循环里写我建议写清晰一点from typing import List from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: q deque() # 存下标按照 nums 的值从大到小排列 res [] for i, x in enumerate(nums): # 1. 去除已经不在窗口内的队首元素 if q and q[0] i - k 1: q.popleft() # 2. 从队尾开始把所有值小于等于当前值的下标全部移出 while q and nums[q[-1]] x: q.pop() # 3. 当前元素入队 q.append(i) # 4. 当窗口已经形成时记录队首元素 if i k - 1: res.append(nums[q[0]]) return res这里的关键点有两个第一为什么队内要存下标而不是直接存数组值因为光凭值你无法判断这个元素是否还在窗口内。滑动窗口每次移动旧的元素可能已经过期你需要根据下标来判断。而且值相同的两个元素虽然值一样但过期时间不同所以依然要区分它们。存下标是更稳妥的做法。第二维护单调性时用还是如果用遇到和当前元素相等的旧元素会把它从队尾弹出去。这样会让队列里的元素尽量新下标更大效果是如果最大值有多个相同值时队首元素会倾向于最新的那一个。用也可以但保留更久的相等元素有时会让过期检查更慢。所以统一用是常见且更简洁的写法。我还会在滑动窗口问题里做一个提前优化如果窗口长度k等于1那答案就是数组本身如果k大于等于数组长度只需要返回整个数组的最大值。这些边界条件虽然不会影响主逻辑但提前判断能让思路更清晰。3.4 时间和空间复杂度单调队列为什么是最优解每个元素最多被入队一次、被弹出一次所以总操作次数是O(n)时间复杂度是O(n)空间复杂度是O(k)因为队列里最多同时存放k个元素。这个复杂度已经是最优了因为你要输出的结果数组本身就有n - k 1个元素至少也要O(n)的时间去生成结果。单调队列是这道题的标准解法。我在做这道题时还想过用“大顶堆懒删除”的思路用堆记录窗口内的元素每次移动窗口将要移除的元素标记为过期堆顶如果过期就弹出。时间复杂度也是O(n log n)或O(n log k)。这种做法的优点是思路直观缺点是需要额外处理“过期元素”的标记代码反而更啰嗦。对于本题单调队列是最直接、最轻量的解法。但如果你在面试中想扩展思路提一句“也可以用堆做但需要懒删除”会是加分项。4. 347 前 K 个高频元素哈希统计之后的选择题4.1 数据流视角为什么先排序不一定是最优解前面两题一个是栈、一个是队列到这一题就开始加新东西了。题目要求返回前K个高频元素直觉上的做法分两步用哈希表统计每个元素出现的次数。根据次数排序取前K个。第一步没有任何争议问题出在第二步。如果对全部频率排序时间瓶颈是O(n log n)但题目只要求前K个K可能远小于n这时候有更合适的思路只维护一个大小为K的堆。具体来说维护一个小顶堆堆里保存“当前出现频率最高的K个元素”。当新元素频率高于堆顶元素时把堆顶弹出把新元素加进来。这样堆里始终是前K个最大频率的元素。整个过程只对这K个元素排序时间开销是O(n log K)。当K比n小很多时效率优势很明显。如果你是跟着代码随想录一路刷过来的其实早就见过这种思想用堆去求“前K个最大”时用的是小顶堆而不是大顶堆这个反直觉点值得停下来想明白。4.2 最大的坑求TopK最大的元素为什么用最小堆如果我想维护前K个最大值常规直觉是我应该用一个数据容器里面随时放着当前最大的K个。如果容器满了下一个元素比容器里某个元素大就把最小的那个替换掉。用什么才能最快知道容器里的最小值小顶堆。大顶堆的顶部是堆中最大的元素但你根本不需要知道最大的那个你需要的是边界——也就是这K个元素里最小的那个。只要有比它大的新元素进来它就离开TopK新的更大的进来。所以小顶堆才是TopK最大值的正确选择。相反如果题目要求前K个最小的元素则用大顶堆因为你要快速知道当前TopK里最大的那个以便被更小的替换。这个思维方式一开始很容易惯性搞反。我当年第一次做这类题时想都没想就建了大顶堆结果发现只能拿到最大值无法直接维护TopK的边界最后多写了一大堆判断逻辑。记住这句话求最大TopK用最小堆求最小TopK用最大堆。4.3 Python里的heapq与Counter结合实现Python的heapq默认是小顶堆。用它做这道题特别顺手from typing import List from collections import Counter import heapq class Solution: def topKFrequent(self, nums: List[int], k: int) - List[int]: freq Counter(nums) # 维护一个小顶堆元素是 (次数, 值) heap [] for num, count in freq.items(): if len(heap) k: heapq.heappush(heap, (count, num)) else: if count heap[0][0]: heapq.heapreplace(heap, (count, num)) # 堆里存的是前K个高频元素结果顺序随便 return [item[1] for item in heap]有几个细节需要说明堆元素用(count, num)这样heapq会比较元组的大小先比较count如果count相等再比较num。这个特性有时会导致相同频率的元素排序不稳定但对本题不影响。heapq.heapreplace会先弹出堆顶再压入新元素比heappop加heappush更高效而且保证堆的大小始终为K。如果len(heap) k直接heappush不要先判断再去替换否则堆还没满就漏掉了元素。返回的时候堆里的顺序不是严格频率从大到小但题目没有要求结果顺序所以直接返回即可。如果遇到面试官追问“能按频率从大到小返回吗”可以再对堆排个序或者用Counter的most_common(k)。其实在Python里这道题还有更简洁的写法from collections import Counter class Solution: def topKFrequent(self, nums: List[int], k: int) - List[int]: return [num for num, _ in Counter(nums).most_common(k)]most_common底层其实也是用堆来实现的。但为了真正理解原理还是建议手动写一遍heapq版本否则面试时只能说出答案说不出过程。4.4 和排序方案的对比什么时候可以无脑排序如果K接近n比如要从100个元素里取前99个用堆和用排序的时间差异很小排序的代码还更短。但如果是海量数据比如1亿个元素取前100个高频排序的O(n log n)就非常吃紧而堆版的O(n log K)几乎可以忽略K的影响。另外Counter.most_common(k)在内部是用了nlargest这类算法的它在某些情况下会用快排的变体算法复杂度是O(n log k)而不是严格的堆操作。所以日常刷题用most_common完全够用想深究算法再去手写堆。这种“同一道题在不同规模下用不同策略”的意识是刷题提升的关键。347题看起来只考“哈希堆”实际考的是你能否识别出TopK问题的本质不需要全排序只需要维护一个大小为K的候选集。5. 栈与队列的武器库这三道题教会我的选型思路5.1 栈擅长“回溯现场”队列擅长“保持时序”150题中我们利用栈存储最近的两个操作数。这个场景的本质是后出现的数字需要先参与运算。递归、括号匹配、函数调用栈、浏览器后退全都是同一类“回到上一个状态”的需求。队列的场景则相反滑动窗口需要保持元素从进入窗口到离开窗口的先后顺序。如果只用栈你很难判断哪个元素先离开窗口因为栈的出口在末尾。所以时序性数据天然属于队列。那单调队列是怎么进阶的它在普通队列“先进先出”的基础上加入了一个内部规则尾部入队前先把破坏单调性的旧元素清理掉。这使得队列头部不再只是“最先进入的元素”而成了“当前剩下的最大值”。这个操作不改变队列的“时序骨架”只是因为窗口里的旧元素会被淘汰所以队列前面的一部分元素可能提前从尾部被弹出了。保持数据结构核心性质的前提下增加自定义规则这是算法设计里非常常见的手段。5.2 单调队列的使用前提与失效场景什么样的场景适合用单调队列对应到滑动窗口类问题窗口往右滑动每一步需要当前窗口的最值而且你希望O(1)得到答案。除了“滑动窗口最大值”单调队列还能解决“滑动窗口最小值”“滑动窗口的中位数”结合有序结构以及一些“求区间最值”的变种。但单调队列不是万能的。如果查询不是按固定顺序滑动的而是随机的区间查询应该用线段树或稀疏表如果窗口长度会动态变化而不仅仅是左端点单调递增就需要更复杂的结构。另外单调队列只能高效维护“最值”如果要维护“窗口内元素的次序”它就不合适了。5.3 优先级队列的选择逻辑TopK问题的通用答案“前K个高频元素”是TopK问题的一种TopK问题的通用模板是用小顶堆维护K个候选者。不论问题是“最大”还是“最小”核心都是“维护边界”而不是“维护极值”。用到的Python库heapq虽然只提供小顶堆但可以通过取负数模拟大顶堆。例如如果求前K个最小元素可以存(-count, num)或者直接调整比较规则。这个技巧在TopK相关题目里反复出现值得专门练一手。5.4 三种结构的对比总结需求特征推荐结构典型题目时间复杂度最近相关、回溯现场、后进先处理栈150逆波兰表达式求值、括号匹配、函数调用消解O(n)先进先出、按时间顺序、窗口滑动队列/单调队列239滑动窗口最大值、滑动窗口最小值O(n)需要找到前K大/前K小、动态插入与淘汰优先级队列堆347前K个高频元素、数据流中的中位数O(n log k)这张表是我刷完这几道题后反复琢磨的结晶。以前我总觉得栈和队列只是两种“顺序相反”的容器现在才知道它们的本质差异在于“你希望遗忘哪些元素”以及“你希望保留哪些信息”。栈保留最近队列保留最早单调队列保留“既新又有价值的”堆保留“当前最需要被替换的”。6. Day10结束后的自测建议与常见问题排查视角6.1 如何判断自己真掌握了这三道题光看题解不算会我给自己定了三个自测标准不看代码能用自己的话把逆波兰表达式的入栈出栈流程讲清楚包含操作数的弹出顺序。能解释为什么单调队列里要存下标以及为什么新元素入队时要弹出所有值较小且下标更靠前的元素。能解释为什么TopK最大的K个数用小顶堆并现场手写heapq版本而不用most_common。三个都能做到才算真正过关。如果你还想更稳可以把这个标准反向使用拿着这三道题去面试大概率会被追问“还有没有别的做法”、“如果K特别大怎么办”、“如果数据上升到内存放不下怎么办”。6.2 面试里常见的变体追问关于150题面试官可能会让你实现一个计算器支持括号和加减乘除这就是中缀表达式求值核心步骤是先把中缀转成后缀再调用今天的求值逻辑。关于239题面试官可能把窗口改成固定长度的流式数据让你维护实时最大值这本质还是单调队列。关于347题面试官可能把数据改成流式输入无法一次统计完频率这就要考虑用外部排序、分治或者分布式统计。虽然这些变体听起来更复杂但基础都离不开今天这三个数据结构。6.3 关于代码随想录Day10的总结方式我刷到这一天时没有急着往后再刷而是把三道题的代码重新手写了一遍又把这篇文章里那些“为什么”用白板画了一遍图。这个过程花的时间比第一次刷题还长但收获明显更大。代码随想录的章节顺序本身就在引导你不断回顾和总结每次总结不一定要写很长的博客哪怕是在本子上画一张“栈/队列/堆选型流程图”都是好的。如果你也在跟着刷建议你在Day10结束后的第二天关掉题解再做一遍这三题。能连续通过才算把这一天的内容真正装进脑子里。后面的学习会更依赖这种扎实感毕竟栈与队列只是数据结构体系里的一小块把这三天的基础打牢后面二叉树、图论里的很多思路都会变得顺畅许多。