刷算法题刷到代码随想录day11的栈与队列part2也就是20.有效的括号、1047.删除字符串中的所有相邻重复项、150.逆波兰表达式求值这三道经典题时我最大的感受是栈终于开始干正事了。前面part1用栈实现队列、用队列实现栈更多是结构层面的互相模拟而这三道题直接让栈站到了第一线——括号配对的嵌套校验、字符串相邻字符的连锁消除、后缀表达式的求值计算全都在考验同一个能力如何高效地“回看最近的关键信息”。这篇文章就把我这天的完整刷题过程、踩过的坑和解题思路整理出来如果你正在按代码随想录刷题或者准备算法面试这部分内容可以直接抄作业。1. 栈与队列part2到底在练什么三道题背后的共同规律1.1 从part1到part2先会互相模拟再谈真正应用代码随想录的题目顺序是有讲究的。part1里的232.用栈实现队列和225.用队列实现栈本质上是让你先搞清楚两种数据结构的核心差异栈是先进后出LIFO队列是先进先出FIFO。你只有在实现层面把这两个特性吃透了到了part2面对“匹配、消除、计算”这类真实场景时才会自然地想到用栈去解决。我见过不少人刷题时跳过part1直接做part2结果做到150.逆波兰表达式求值的时候会纠结“为什么这里用栈而不用队列”其实答案早在part1就埋下了栈能保留最近的顺序队列只能保留最老的顺序。而括号匹配、相邻消除、表达式求值全都依赖于“最近的信息优先处理”这个规律所以栈是唯一正确的选择。1.2 匹配、消除、计算栈的三个经典应用场景把这天的三道题放在一起看它们其实是同一种底层模式的不同变体有效的括号本质上是一个嵌套结构的对称性校验内层的括号必须比外层的先闭合这是一个典型的“后进先出”过程。删除字符串中的所有相邻重复项当前字符和它“左边最近的那个未消除字符”做比较相同就一起消失。这个“最近”二字就是栈顶元素。逆波兰表达式求值操作数按顺序进来遇到运算符就取最近的两个操作数做运算结果再压回去。整个过程完全不依赖运算符优先级因为顺序已经被后缀表达式固定好了。三道题都离不开“记住最近状态”这个动作。栈顶操作是O(1)的每次只需要看栈顶、压栈、弹栈代价极低所以这类题用栈解起来又自然又高效。1.3 面试官视角为什么这三道题值得反复刷这三道题在面试里的出场率非常高尤其是有效的括号我可以说十个考栈的面试官里至少有七八个会问它或者它的变体。原因也很简单这三道题的代码量都不大但它们把边界情况藏在了细节里——空栈能不能访问、最后栈里还有没有残留、运算符弹出时谁先谁后。能把这些边界问题处理干净说明候选人的代码严谨度是过关的。更关键的是这三道题是后面一系列进阶题目的地基。理解了“用栈做相邻匹配”再去看单调栈、表达式解析、浏览器前进后退的实现都会觉得顺理成章。所以别嫌它们简单值得多刷几遍。2. 有效的括号一场逐层的对称性校验2.1 题目理解与暴力解法的局限题目要求是给定一个只包含小括号、中括号、大括号的字符串判断这个字符串中的括号是否合法。合法的意思有两个层面左右括号数量对得上而且嵌套顺序必须正确。像([)]这种虽然三种括号数量都齐了但因为交叉嵌套是不合法的。如果不考虑栈直观的做法是递归找到一对匹配的内层括号消掉之后继续判断。比如[()]先消掉中间的()剩下[]再消掉。但这个思路写起来非常啰嗦每次都要扫描字符串找配对的括号时间复杂度最坏能到O(n^2)。而且递归本身还会带来额外的栈空间消耗。所以面试中一旦你提出递归解法面试官大概率会追问一句“能不能用栈做一次遍历搞定”2.2 栈解法核心思路遇到的右括号必须匹配最近未闭合的左括号用一个栈保存“还没闭合的左括号”。遍历字符串的时候遇到左括号就压栈遇到右括号就判断它是否等于当前栈顶的那个左括号。如果相等说明这个右括号恰好闭合了最近的那个左括号把栈顶弹出如果不相等说明括号类型错位了直接判定非法。这里有一个小技巧值得记住压栈的时候与其压入左括号本身不如直接压入它对应的右括号。这样遇到右括号时只需要比较栈顶是否等于当前字符连map都不用建。代码随想录的写法也是这个思路测下来确实是最简洁的。class Solution { public: bool isValid(string s) { // 奇数长度的括号串一定无法完全配对先剪枝 if (s.size() % 2 1) return false; stackchar st; for (char c : s) { // 遇到左括号把对应的右括号压栈 if (c () st.push()); else if (c [) st.push(]); else if (c {) st.push(}); // 遇到右括号栈空说明没有可配对的左括号 // 栈顶不相等说明类型错位比如 (] 的情况 else if (st.empty() || st.top() ! c) return false; else st.pop(); } // 循环结束栈还不为空说明有左括号没有被闭合 return st.empty(); } };2.3 三个必踩的坑剪枝、哨兵和残留检查第一个坑是奇数长度直接返回false。这个剪枝很简单但很多新手会漏掉。虽然漏掉也能被后面的逻辑拦截但加一个长度判断可以减少不必要的遍历也让面试官觉得你考虑问题更全面。第二个坑是遇到右括号时必须先判断栈是否为空。如果字符串是()]遍历到]的时候栈里已经空了此时访问栈顶就是一个未定义行为程序直接崩。正确做法是把st.empty()放在st.top() ! c的前面利用短路求值避免越界访问。第三个坑是最后忘了检查st.empty()。如果字符串是(()前两个左括号都被压栈但只有一个右括号来匹配最后栈里还剩一个(这种情况同样不合法。很多人遍历完之后直接return true结果样例(()过不去。这三处细节合在一起就是这道题考察的重点。2.4 逐行解读代码为什么左括号压右括号更聪明上面的代码里我只写了三个左括号分支然后一个else分支就处理了所有右括号逻辑非常顺滑。原因是左括号出现时它期望的是将来有一个特定的右括号来闭合它所以把期望值直接压入栈中右括号出现时它只需要回答一个问题——“栈顶是不是我这个字符”是就配对不是就失败。如果压入的是左括号本身那遇到右括号时就得再加一个反向映射判断类似if (c ) st.top() ! ()等于多写三个分支还要小心map的使用。压入对应右括号的做法把三类括号统一成了同一个比较逻辑代码量和出错率都降下来了这个习惯在后续的“删除字符串中的所有相邻重复项”里也能复用。2.5 变体与延展从基础题到实际世界的括号匹配只含一种括号的情况很好处理比如()()直接用计数器遇到(加一遇到)减一中途小于零或者最后不为零就是非法。但一旦括号种类多了计数器就失效了因为([)]的计数是平衡的嵌套关系却是错的。这就是为什么要用栈而不是用一个数字来记录状态。再把视野放大一点IDE里的代码缩进检查、编译器词法分析阶段的括号匹配、JSON和XML的标签闭合校验本质上都是在做“最近配对”这件事。刷完这道题之后再去理解这些工具的实现会觉得亲切很多。3. 删除字符串中的所有相邻重复项消消乐的栈版本3.1 题目理解与为什么用栈天然契合题目示例是abbaca第一步看到两个相邻的b消除后变成aaca此时aa又相邻了继续消除最后剩下ca。这种连锁消除的难点在于你删掉一对字符后原本不相邻的字符可能重新变成相邻然后引发新的消除所以不能只简单遍历一次。栈天然契合这个问题因为它的栈顶就是“最近的还没被消除的字符”。遍历到当前字符时如果它和栈顶相同说明这两个字符是相邻重复的直接把栈顶弹掉如果不同说明现在没有可消除的先把当前字符压栈等后面的字符来跟它配对。3.2 核心实现逻辑相同就弹栈不同就入栈我自己喜欢用string直接当成栈来用省去最后拼接的麻烦。核心判断逻辑只有一行当前字符等于栈顶字符的时候弹栈否则压栈。因为栈顶始终代表“字符串当前尾部还没被消除的那个字符”所以这个比较天然就是相邻比较。class Solution { public: string removeDuplicates(string s) { string res; // 直接当成栈使用 for (char c : s) { if (!res.empty() res.back() c) { res.pop_back(); // 相邻重复消除 } else { res.push_back(c); // 暂时没得消除进栈等待 } } return res; } };跑一遍示例res从空开始遍历第一个a压栈此时resa第二个b不等于栈顶a压栈resab第三个b等于栈顶b弹栈resa第四个a等于栈顶a弹栈res第五个c入栈resc第六个a入栈resca。整个过程就是消消乐只是把消掉的逻辑搬到了栈里。3.3 代码讲解与复杂度分析res.empty()的判断不能省。如果你直接对空字符串调用back()行为是未定义的在LeetCode的测试环境里大概率直接报错。这就是栈题里最经典的“访问空栈”问题和2.3节里提到的坑一脉相承。时间复杂度是O(n)因为每个字符最多入栈一次、出栈一次完全线性空间复杂度最坏是O(n)比如字符串没有相邻重复项的时候所有字符都留在栈里。如果直接用std::stackchar最后还需要把栈里的字符依次取出再反转而用string当栈返回值直接就是想要的答案省了一步操作。3.4 为什么用string当栈比stack 更舒服std::string底层是动态数组push_back和pop_back都是摊还O(1)的操作拿它当栈完全没问题。它比std::stackchar多出来的好处是能直接返回字符串结果而stack还得手动倒数据。很多讲解代码会忽略这个细节我实测下来面试场景里用string当栈会显得更熟练代码也短。当然理解层面还是要明确string在这里就是栈的替身别因为这个技巧就混淆了字符串和栈的区别。用std::stack走一遍标准流程再用string优化两层都吃透最好。3.5 和真实开发场景的连接撤销、历史记录与文本编辑器栈的“回看最近状态”能力在开发工具里无处不在。最典型的是文本编辑器的撤销功能——每次编辑操作被压入一个操作栈按CtrlZ就从栈顶弹出一个操作并还原。浏览器的后退按钮也是同一个模型把访问过的页面压进栈后退就是弹栈。更贴近这道题的是编辑器里的“相邻字符处理”比如你写了一篇Markdown连续删掉两个同样的字符、或者自动配对引号变成双重引号代码里处理这些逻辑时背后往往就藏着一个栈。刷完这道题之后再看这些工具的实现思路会比之前清晰很多。4. 逆波兰表达式求值从人脑到栈的运算规则转换4.1 什么是逆波兰表达式后缀表达式为什么被发明出来我们平时写的1 2 * 3是中缀表达式运算符在两个操作数中间读起来符合直觉但计算机处理它需要额外考虑运算符优先级和括号。逆波兰表达式也叫后缀表达式把运算符放到操作数后面比如1 2 3 * 它不需要括号也不需要优先级规则因为表达式的顺序已经把计算次序固定了。这个想法来自波兰逻辑学家卢卡西维茨所以叫“逆波兰”。“逆”是因为正常波兰表示法是前缀运算符在操作数前面他这个是把运算符放后面。很多老式计算器尤其是HP的工程计算器至今仍使用RPN输入方式输入数字按回车压栈按运算符弹栈计算和这道题的逻辑完全一样。4.2 用栈模拟运算过程数字入栈运算符触发归约求值规则很简单遇到数字就压栈遇到运算符就从栈顶弹出两个数做运算再把结果压回栈里。这里有一个非常容易错的细节先弹出的是右操作数后弹出的是左操作数。拿示例跑一遍[2,1,,3,*]。先是2入栈再是1入栈遇到弹出1作为num2、弹出2作为num1计算213把3压回栈。接着3入栈遇到*弹出3作为num2、弹出3作为num1计算3*39最终栈顶就是9。这里为什么先弹出的是右操作数因为表达式是顺序进入的越晚进入的数字在栈顶而数字进的顺序就是从左到右所以栈顶对应右边的操作数它的下面那一个才是左边的操作数。减法和除法尤其依赖这个顺序。class Solution { public: int evalRPN(vectorstring tokens) { stacklong long st; for (string s : tokens) { if (s || s - || s * || s /) { long long num2 st.top(); st.pop(); long long num1 st.top(); st.pop(); if (s ) st.push(num1 num2); else if (s -) st.push(num1 - num2); else if (s *) st.push(num1 * num2); else st.push(num1 / num2); // 整除 } else { st.push(stoll(s)); // 字符串转 long long } } return (int)st.top(); } };4.3 两个必踩的细节坑操作数顺序和整除方向第一个坑就是4.2节说的减法顺序。表达式[5,3,-]正确结果是5-32。如果弹出后算num2 - num1就会变成3-5-2样例直接过不去。除法同理[4,2,/]正确是2算反了会得到0因为2/40。每道栈题里都藏着一个操作数的顺序问题这道题是最典型的。第二个坑是整除方向。C的整数除法是向零截断的比如-3 / 2 -1这恰好符合这道题的要求。但如果你用Python做默认的//是向下取整-3 // 2会得到-2就错了。在Python里想保持向零截断得写成int(num1 / num2)用浮点数除法之后截断我这里特别提醒一下跨语言刷题的朋友。4.4 为什么编译器最终选择了后缀表达式中缀表达式对计算机来说并不友好因为1 2 * 3必须知道*的优先级高于这需要额外的规则或者括号。编译器在处理表达式时通常会把中缀转成后缀再顺序求值。转换的经典算法叫调度场算法用两个栈分别保存运算符和输出结果遇到低优先级运算符时就把高优先级的先弹出去。这个过程本质上就是把“人的阅读习惯”翻译成“机器的线性处理方式”。后缀表达式还可以直接对应表达式树的后序遍历树的中序遍历是中缀后序遍历就是后缀。理解了这道题后面再接触编译原理里的表达式解析就会觉得编译器这么做是有道理的因为它最大程度利用了栈的顺序性。4.5 边界情况与实际工程中的提醒实际写的时候要小心除数为零LeetCode的测试数据里一般不包含但自己练习时可以额外判断一下。另一个容易被忽略的是中间结果溢出题目允许的整数范围很大中间计算可能超出int的范围所以我代码里用long long来存操作数和中间结果最后再转回int这样最稳。工程实践里如果自己写一个基于RPN的计算器还需要考虑数字里包含负号的情况比如-4看起来像运算符实际是数字。LeetCode的测试数据中负数可以作为操作数出现stoll能正确处理带符号的字符串所以我的代码里把“判断是否是四则运算符”放在最前面剩下的通通按数字处理这个顺序非常关键。5. 三题复盘规律、延伸与刷题节奏5.1 三题核心套路对比一张表看懂共同点刷完三道题之后我建议你合上代码用一张表的形式在脑子里过一遍它们的共性题目核心动作栈的职责时间复杂度空间复杂度20. 有效的括号左右括号配对暂存等待匹配的左括号O(n)O(n)1047. 删除字符串中的所有相邻重复项相邻相同字符消除暂存最近的未消除字符O(n)O(n)150. 逆波兰表达式求值表达式运算暂存中间操作数O(n)O(n)看见没有全是O(n)时间、O(n)空间全都依赖“栈顶是最近信息”这一条。下次遇到一道新题只要问题描述里出现了“最近的”“相邻的”“嵌套的”“向后看”这些关键词第一反应就该是栈。5.2 从这三题延伸出去单调栈、单调队列和优先队列这三题刷完代码随想录的栈与队列专题其实就基本收官了但它们的延伸题更值得留意。比如239.滑动窗口最大值用的是单调队列——队列里的元素保持单调递减每次取队首就是窗口最大值这是“队列”进阶用法347.前K个高频元素用的是优先级队列也就是堆还有后面的单调栈专题像每日温度、接雨水都是利用栈内元素的单调性来求解。另外你在面试中一旦提到队列很容易被追问到工程领域的消息队列Kafka、RabbitMQ、RocketMQ怎么选型线程池的阻塞队列怎么选。这些看起来高大上的名词起点其实就是算法里这个朴素的FIFO队列。生产者-消费者模型、队列的入队出队、顺序保证这些概念在算法题里先打好底子再去理解消息队列的ACK机制、重复消费、顺序消费会轻松很多。5.3 栈在程序运行时的身影函数调用栈与栈帧形成过程栈的应用远不止算法题。程序运行时每一次函数调用都会在系统栈上分配一个栈帧栈帧里保存了返回地址、参数、局部变量和寄存器状态。函数开始执行时栈帧压栈函数返回时栈帧弹栈这个“压栈-弹栈”的过程和算法题里的入栈出栈完全一致。理解这件事之后很多概念都能串起来递归能写成函数调用自己的形式是因为系统帮你维护了调用栈递归深度太大会导致栈溢出是因为栈空间是有限的程序崩溃时打印的backtrace栈回溯就是从当前函数一层层往上找把栈帧里的函数名字列出来。甚至那句“C语言局部变量越少占用的栈空间越小”说的也是栈帧里的局部变量区域会更小。这些知识点回到代码层面都指向栈这一个核心结构。5.4 我的刷题经验与节奏建议一天三道题该怎么消化我按代码随想录的节奏刷下来个人体会是一天三道题刚刚好再多就容易走马观花。具体安排可以这样上午先做20.有效的括号下午做1047和150每道题先自己思考15到20分钟想不出来再看题解。题解看懂之后不要急着收工把代码抄一遍然后合上题解自己重新写一遍写到完全不需要看答案为止。第二天早上花15分钟把这三道题再快速过一遍。哪道题卡住了说明那道题的思路还没真正长在脑子里需要再刷一遍。这三道题都不算难但它们是后面所有栈相关题目的地基地基打不牢后面的单调栈、表达式解析、括号生成都会比较吃力。最后分享一个我实际用下来很有用的小习惯刷栈和队列这类题我面前会放一张白纸每遇到一个入栈出栈操作就往纸上写一遍当前栈的状态。刚开始觉得有点多余但刷到day11这三题就会发现能徒手在纸上完整复现栈的变化过程的人和只能对着代码一步步调试的人对栈的理解深度完全是两个层次。栈这个东西只要真正理解了“回看最近”这四个字后面无论是单调栈、逆波兰、函数调用栈还是消息队列的那堆延伸概念都不会再觉得陌生。
