刷算法题最怕的一种状态就是看题觉得很简单一提交发现全是边界问题。今天的训练营打卡内容就是典型20. 有效的括号 和 1047. 删除字符串中的所有相邻重复项两道题都属于“字符串处理 栈”的入门组合代码量都不大但几乎每个训练营群里都会有人翻车。我这次把两道题连在一起刷最大的收获是抓住了它们共用的一个思考方式——用栈做“回退”。这篇文章会把解题过程、易错点、以及我自己总结的栈题套路完整过一遍也希望给正在刷算法题的朋友一点参考。如果你刚开始学数据结构栈这个概念可能很抽象。但这两道题恰恰能把栈讲明白一个讲“匹配”一个讲“消除”本质上都依赖“后进先出”这个特性。题目本身不算难难的是从“看着简单”到“一次写对”之间那段路而这正是训练营里最值得复盘的部分。1. 为什么“栈”是这两道题共同的主角1.1 从处理顺序看本质先别急着写代码想一个问题有效的括号里最内层的括号一定是最先被匹配的。比如{[]}虽然左花括号{最早出现但它要等到最后的}才匹配而中间的[和]反而先配对。这种“后进先出”的顺序和栈完全一致。1047 题也一样。删除相邻重复项时假设字符串是abbac你先看到a然后看到两个b消掉bb之后新的末尾变成了a结果下一个a又和它重复继续消。你发现没有——每次消除后需要回头重新比较的永远是“最近还没被处理掉的那个字符”。这个“最近的一个”恰恰就是栈顶。所以这两道题虽然名字不同一个讲括号合法性一个讲字符串去重但骨子里是同一个模型我都会用一个容器把暂时没法决定去留的元素缓存起来等新元素出现时优先跟最近缓存的元素比一比。1.2 一个“回头看”的判断标准我自己刷题有个习惯看到一个新题目先不翻题解而是问三个问题处理当前元素时需不需要知道上一个还没处理完的元素如果上一个元素暂时不能决定去留能不能先存起来后面某一步会不会反过来用到这个“最近”的元素只要这三个问题里大多是“是”那这道题八成要用栈。拿 20 题举例遇到一个右括号时你要判断它能不能闭合最近的左括号如果最近那个左括号不匹配整个字符串就无效。这完全符合“回头看”的定义。1047 题就更直接了当前字符就是要跟上一个还没被消除的字符比比完要么压栈要么弹栈。这也是为什么我不建议死记“栈适合解决括号匹配”“栈适合解决表达式求值”这种结论。结论记多了题目稍微变形就懵了。记住“是否依赖最近未处理元素”这个判断标准比记住十道题都管用。1.3 队列为什么不能直接替代有一点值得拎出来说清楚为什么这两道题不用队列既然训练营标题是“栈与队列”很多初学者会想队列不也能存元素吗关键区别在比较对象。队列是先进先出队头是最早进来的元素而这两道题每次都比较“最近的元素”。如果你用队列弹出的永远是老早以前进来的字符完全对不上。比如括号匹配时出现右括号}时你需要看的是最近一个未匹配的左括号而不是最先出现的那个左括号。这是栈的天然主场。队列当然也有自己的人生比如 BFS 遍历、滑动窗口、消息队列削峰那些场景强调“先来先处理”。栈和队列不是同一个工具服务的是两种相反的需求。先把这两道题吃透后面再对比队列时你会非常清楚“为什么不能用栈实现一个排队系统”。2. 20. 有效的括号一份匹配清单的三种典型错法2.1 先弄清楚什么才叫“有效”题目给的是只有()[]{}的字符串要判断括号是否有效。有效条件其实就两条左括号必须被同类型的右括号闭合左括号必须以正确的顺序闭合。第二条最容易忽略。([)]这种字符串每个括号类型都有左右数量也对但顺序是错的因为[先于(出现却要在(之前闭合这就是交叉嵌套无效。我把这种字符串当面试时的必考题因为它专门用来拆穿“只数个数不看顺序”的写法。还有几个边界想清楚空字符串返回 true只有左括号比如((false只有右括号比如]]false长度是奇数直接 false因为括号一定是成对的。2.2 三种典型错法你多半中过招先说第一种三个计数器。有人用count1、count2、count3分别记录三种括号遇到左加一遇到右减一最后检查是否全为 0。这个写法对()[]{}有效但对([)]完全失效因为计数器永远不会出现负数最后也是 0可字符串是无效的。原因就是计数器丢了“顺序”信息。第二种遇到右括号直接弹栈但不检查栈空。比如字符串)或())第一个字符就是右括号此时栈还是空的你直接st.pop()就崩了或者访问栈顶报错。即使语言里不报错逻辑上也必须判 false因为没有任何左括号能跟这个右括号匹配。所以记住访问栈顶或弹出之前永远先问一句“栈空了吗”。第三种循环结束后忘记检查栈是否为空。比如(()遍历完所有字符后栈里还剩下一个(说明这个左括号没有被闭合当然是 false。很多人写代码时注意力全放在循环里觉得循环跑完就完事了结果在最后一步栽跟头。2.3 一种更不容易写错的写法压入“期待值”常见的思路是遇到左括号就压入左括号遇到右括号再拿它跟栈顶比较。这种做法没问题但需要维护一个映射表代码会多一些。我更喜欢另一个写法遇到左括号时直接压入它对应的右括号。比如遇到(压入)遇到[压入]遇到{压入}。这样等到遇到右括号时只需要做一件事检查栈顶是不是当前这个字符。是就弹出不是就返回 false。这个写法的好处有两个。第一少写一层 map 查询字符直接跟字符比较逻辑更直白。第二判断条件集中在一个方向遇到右括号时栈空说明没有可匹配的左括号栈顶不相等说明类型不匹配或顺序错误。我个人在实际刷题中比较推荐这种套路尤其在白板面试时代码短思路清楚。2.4 完整代码和复杂度分析C 版本我用 std::stackbool 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; } st.pop(); } } return st.empty(); }Python 版本可以用 list 模拟def isValid(s: str) - bool: if len(s) % 2 1: return False stack [] for ch in s: if ch (: stack.append()) elif ch [: stack.append(]) elif ch {: stack.append(}) else: if not stack or stack[-1] ! ch: return False stack.pop() return not stack时间复杂度 O(n)每个字符最多入栈一次、出栈一次。空间复杂度 O(n)最坏情况是字符串全是左括号比如((((((所有字符全压进栈里。这里可以加一个小优化如果字符串长度是奇数直接返回 false连遍历都不用。虽然理论上复杂度还是 O(n)但能省掉一半跑到最后的开销。3. 1047. 删除字符串中的所有相邻重复项把“消消乐”写进循环3.1 为什么暴力替换的做法不可行先看一个经典例子abba。直观上先删掉相邻的bb剩下aa这两个又相邻重复得继续删最后结果是空串。如果你用常规的循环 replace比如while (aa in s or bb in s ...)会面临两个问题。第一你可能只替换一次就退出循环漏掉了删除后产生的新重复结果返回aa判错。第二每次 replace 都要重新扫描整个字符串如果有连续触发连锁消除最坏复杂度会变成 O(n²)在字符串很长时就很难受了。这个例子正好暴露了问题的本质删除一对相邻重复之后新暴露出来的字符可能又和更前面的字符重复所以需要一种机制能回到“前一个字符”继续比较。这已经明明白白告诉你要用栈。3.2 核心过程扫描、比较、弹出、回退我用abbaca完整走一遍题目要求的输出是ca读入a栈空直接压入栈为[a]读入b栈顶是a不相等压入栈为[a, b]读入b栈顶是b相等弹出栈为[a]读入a栈顶是a相等弹出栈为[]读入c栈空压入栈为[c]读入a栈顶是c不相等压入栈为[c, a]。最后把栈里的字符拼起来得到ca。注意第三步到第四步的过程弹出的瞬间相当于把刚才存入的那个b撤销了随后新读入的a自动跟更早的a比较。这个“撤销后再比较”的动作就是栈题里最迷人的地方。它看起来像是回头走了一步但栈帮你把这个回头动作做成了 O(1) 的常数时间操作。3.3 三种实现方式从朴素到优化第一种Python 的 list 模拟栈def removeDuplicates(s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)这个写法最简单逻辑一目了然适合作为第一版答案。第二种C 直接用 string 当作栈。因为 string 本身就支持push_back、pop_back、back这些操作天然就是 char 类型的栈string removeDuplicates(string s) { string result; for (char c : s) { if (!result.empty() result.back() c) { result.pop_back(); } else { result.push_back(c); } } return result; }这个做法有个额外好处最后返回的就是栈本身不需要再做一次拼接。第三种原地双指针优化。既然栈里的内容就是结果字符串而且题目允许修改原字符串那么可以用一个 write 指针模拟栈的大小把原数组当成栈空间。扫描时如果当前字符和s[write-1]相等说明栈顶和当前字符重复write--表示弹出否则把当前字符写到s[write]位置然后write。最后把字符串截断到 write 长度string removeDuplicates(string s) { int write 0; for (char c : s) { if (write 0 s[write - 1] c) { write--; } else { s[write] c; } } s.resize(write); return s; }这个版本空间复杂度为 O(1)只用了几个整型变量不额外开辟栈空间。它本质上是“用数组手写了一个栈”。我建议你先把朴素写法搞懂再来看这个优化不要一上来就用地板优化否则容易看不懂。3.4 时间空间与调试心得时间复杂度 O(n)空间复杂度根据实现方式不同朴素版 O(n)双指针版 O(1)。这块我吃过一次亏说说调试心得。刚开始写的时候我习惯在循环里打印当前字符和栈顶但需要注意的是不能只盯着“相等就弹出”这个分支。真正容易出问题的是“栈空时”的情况如果栈是空的访问stack[-1]会越界所以在判断时一定要把stack非空放在前面写成if stack and stack[-1] chPython 里顺序不能反C 里同样要先判断!result.empty()。很多人一上来就写if (result.back() ch)遇到空栈就去访问直接崩掉。还有一个细节是大小写敏感性。题目里没说忽略大小写所以A和a不算重复。刷题时别自己给题目加条件这属于读题不仔细的锅。4. 两道题一起刷我总结出的栈题解题模板4.1 四步拆题法把这两道题放在一起复盘我提取出一个可复用的思考流程暂时叫它“四步拆题法”。第一步判断场景处理当前元素时需不需要跟“之前出现过的最近元素”做比较需要就往栈上想。第二步确定栈的语义栈里存什么20 题存的是“期待的右括号”也可以存左括号1047 题存的是“还没被消除的字符”。语义不同代码结构完全不同。有些题存索引有些题存数值还有些题存计数器。第三步写清入栈出栈条件什么时候压入什么时候弹出这一步是代码核心尽量写成条件分支别混在同一个 if 里。第四步想结果怎么还原栈最后是中间结果怎么变成真正的答案20 题要求返回布尔值直接看栈空不空1047 题要返回字符串需要把栈拼起来或者直接用 string 当栈连拼接都省了。我把两道题整理成一张对照表题目栈里存什么入栈条件出栈条件结果20.有效的括号期待的右括号遇到左括号栈顶等于当前右括号最后栈空则 true1047.删除相邻重复未消除的字符当前字符不等于栈顶当前字符等于栈顶剩余栈元素拼接这样一比较你会发现两道题的本质非常接近都是当前元素和栈顶比较相等就走“消除/匹配”路线不相等就走“入栈”路线。只是 20 题需要额外处理“三种类型括号”的映射关系。4.2 判空是栈题的命门刷了这么多栈题我最想强调的一点是判空。几乎所有栈相关的 bug都是从“访问了不存在的栈顶”开始的。我见过太多类似的代码遇到右括号直接st.pop()忘了先检查st.empty()看到栈不为空但忘记循环结束后还要检查或者在栈顶比较时不判断栈是否为空导致 undefined behavior。这类问题在 LeetCode 上不一定每次都崩因为语言和编译器不同表现也不太一样但逻辑一定是错的。我给自己定了一条规则写任何栈题凡是涉及top、pop、back的操作先写判空。哪怕这题不可能出现空栈访问也要保留判断因为代码的可读性和防御性比少写一行更重要。面试时这个习惯非常加分它说明你考虑过边界。4.3 用数组或字符串代替标准栈的实用技巧一开始刷题时我默认用语言自带的 stack 类后来发现不少场景里用数组或字符串模拟栈更顺手。先说 C。std::stack 是一个容器适配器默认底层是 std::deque操作上有push、pop、top。但如果你最终要按顺序输出栈内元素stack 的遍历并不方便得先把元素倒腾到另一个容器里。相反用 vector 或 string 模拟栈既能当栈用又保留了顺序访问的能力。1047 题直接返回 string 当栈就是这种思路的极致体现。Python 里同理list 本身就是最好的栈append 和 pop 都是 O(1)还能直接遍历。很多从 Java 转过来的人习惯去 import Stack 类其实没必要。Java 官方也不推荐再用 Stack 类更建议用 ArrayDeque。语言细节因环境而异但核心思想一样普通栈操作用动态数组模拟效率高、可控性好。当然如果元素类型比较复杂比如需要存(字符, 出现次数)这种 pair直接用一个 stackpairchar, int 或者 vectorpairint, int 都可以。只要你能保证压入和弹出的顺序符合“最近优先”用什么容器反而不重要。5. 进阶一击这两道题的常见变形5.1 从“有效的括号”出发的三条升级路线20 题后面通常接着三道题难度逐步上升我建议按这个顺序刷。第一道是 22. 生成括号。它要求生成所有有效的括号组合思路是回溯在递归过程中维护一个“当前已生成的括号串”。判断某个状态是否合法时可以沿用 20 题的计数思路右括号数量不能超过左括号数量左括号数量不能超过 n。这道题用栈也能解但回溯 剪枝更主流它让你明白括号合法性的另一种表达方式。第二道是 32. 最长有效括号。这道题难度明显上来了常见的做法是栈里存索引而不是存字符。栈里先放一个-1作为基准遇到左括号入栈遇到右括号弹栈再用当前索引减去新的栈顶索引得到目前为止连续有效的长度。为什么不直接存括号字符因为你需要用索引来计算长度。这就是“栈的语义”变化带来的思维挑战也是 20 题之后很值得做的一道延伸。第三道是 678. 有效的括号字符串。它引入了一个通配符*可以当左括号、右括号或者空字符。经典做法是双栈或者两个计数器一个栈存左括号位置一个栈存星号位置最后统一配对。这个玩法已经远超 20 题基础范围了但能让你彻底理解“括号匹配”的多种条件。另外还有 71. 简化路径也属于括号题之外的“栈模拟”延伸题本质是用栈来处理路径片段和..回退。刷完 20 题后直接做这道会有一种熟悉感。5.2 从“删除相邻重复”出发的同类题目1047 题也有一个教科书级别的扩展就是 1209. 删除字符串中的所有相邻重复项 II。区别在于原始题是删除相邻的两个相同字符而这道题要求删除相邻的 k 个相同字符。解法几乎就是把 1047 的思路稍微升级栈里存的不是单个字符而是一个包含字符和连续次数的结构。每新来一个字符如果和栈顶字符相同就把栈顶的次数加一当次数达到 k 时弹出栈顶。如果不同就压入一个新的节点次数从 1 开始计。我给一个简单的 Python 版本def removeDuplicates(s: str, k: int) - str: stack [] for ch in s: if stack and stack[-1][0] ch: stack[-1][1] 1 if stack[-1][1] k: stack.pop() else: stack.append([ch, 1]) return .join(ch * count for ch, count in stack)这个变形题的识别信号很清晰从“删相邻两个”变成“删相邻 k 个”本质上就是要你额外维护一个计数。只要你理解 1047 的“栈顶比较 弹出”模式1209 也只是一层窗户纸。5.3 栈题的共同识别信号刷多了以后我对哪些题适合用栈有了条件反射。描述里如果出现“相邻”“最近”“回退”“成对出现”“闭合顺序”大概率跟栈有关。现实生活里的例子也很好记编辑器撤销是栈浏览器后退按钮是栈函数调用时的栈帧也是栈。你写递归时系统编译器就在背后维护一个调用栈。所以在做题时如果题目要求你模拟“撤销”或“回滚”行为先想想能不能用栈表达。这种识别信号比刷题数量的价值更大因为它能帮你在面对新题时快速定位数据结构方向。6. 和队列一起看什么时候该换工具6.1 队列的经典“排队”场景虽然今天这两道题都是栈的主场但训练营标题既然写了“栈与队列”还是值得把队列一起拉出来看。队列这种先进先出的结构适合处理“按顺序、先到先处理”的问题。最常见的算法场景就是 BFS 广度优先搜索从起点开始先把第一层邻居入队再逐层向外扩展每一层都必须按入队顺序处理这时候栈就不合适了。类似的还有滑动窗口最大值那题用的是“单调队列”在窗口中维护一个有序队列让队头始终是最大值。在工程上消息队列也是队列思想的体现。生产者和消费者解耦数据先放到队列里再由消费方按顺序处理。面试系统设计时经常会聊到 kafka、rabbitmq、rocketmq 的选型核心关注点就在顺序性、可靠性和吞吐量。这跟咱们刷题时学的“先进先出”是一脉相承的只是落到了分布式系统里。6.2 栈和队列怎么快速做选择我总结了一个简单判断法新元素需要和谁比较谁先被处理决定了用栈还是队列。新元素要和“最近”的元素比较后到的先触发处理逻辑用栈新元素要和“最早”的元素比较或必须严格按到达顺序处理用队列。举几个例子括号匹配是跟最近的左括号比用栈打印任务排队是老的先打用队列函数调用返回时后调用的函数先返回用栈。这个判断法基本能覆盖九成以上的基础数据结构题。6.3 一个容易忽略的点栈题也能嵌套队列思维栈和队列并非水火不容。有些题表面是栈实际却要结合别的数据结构。比如最小栈题要求设计一个栈能在 O(1) 时间内拿到底部的最小值。经典做法是用两个栈一个正常存数据另一个只存“当前出现过的最小值”每次 push 或 pop 时同步更新。这里底层思想是“单调性维护”和单调队列有异曲同工之处。还有一种做法用一个主栈加一个辅助栈也属于空间换时间的思路。我提这个是想提醒你数据结构往往是组合使用的别做了一道栈题就只想着栈。等训练营后面接触到单调栈、堆那一类内容时你会更深刻地感受到栈只是一个工具真正值钱的是“你能识别出问题在问什么”。回到今天这两道题我觉得最大的价值不是 AC 的瞬间而是把“最近元素优先处理”这个模型真正建立了。有了这个能力后面再碰表达式求值、逆波兰表达式、简化路径、接雨水、柱状图中最大的矩形思路会顺很多。我个人在实际刷题时还有个习惯每道栈题写完都手动跑三个特殊例子——空输入、单个字符、全部重复字符。这三个例子能一次性暴露栈空和循环结束后的状态问题也推荐你试试。