题目描述
思路解析动画文字版
一句话套路:括号天然是嵌套结构,用栈把「外层还没拼完的片段」存起来,遇到右括号就把内层翻好的片段拼回去。下面一个字符一个字符地走一遍。
开局:当前层片段 cur 为空,栈也是空。指针即将从最左字符开始,逐个读入。栈里存的是「进入括号前还没拼完的外层片段」。
读到第 1 个字符 ( :要进入更深一层括号了。先把当前层已经拼好的片段 cur="空" 压进栈保管。
把 cur="空" 压入栈(成为新栈顶),再把 cur 清空。现在进入内层,cur 重新开始拼。
读到第 2 个字符字母 u :它属于当前层,直接追加到 cur 末尾。
追加后当前层片段 cur="u"。栈不变,继续往右扫下一个字符。
读到第 3 个字符 ( :要进入更深一层括号了。先把当前层已经拼好的片段 cur="u" 压进栈保管。
把 cur="u" 压入栈(成为新栈顶),再把 cur 清空。现在进入内层,cur 重新开始拼。
读到第 4 个字符字母 l :它属于当前层,直接追加到 cur 末尾。
追加后当前层片段 cur="l"。栈不变,继续往右扫下一个字符。
读到第 5 个字符字母 o :它属于当前层,直接追加到 cur 末尾。
追加后当前层片段 cur="lo"。栈不变,继续往右扫下一个字符。
读到第 6 个字符字母 v :它属于当前层,直接追加到 cur 末尾。
追加后当前层片段 cur="lov"。栈不变,继续往右扫下一个字符。
读到第 7 个字符字母 e :它属于当前层,直接追加到 cur 末尾。
追加后当前层片段 cur="love"。栈不变,继续往右扫下一个字符。
读到第 8 个字符 ) :这一层括号结束。先把当前层片段 cur="love" 原地反转。
把这一层片段反转:"love" 变成 "evol"。这就是「从内到外」里当前这一层翻好的结果,马上拼回外层继续。
弹出栈顶的上一层片段 "u",把它接在反转后片段前面,合并成新的 cur="uevol"。这一对括号结算完毕,回到上一层继续。
读到第 9 个字符字母 i :它属于当前层,直接追加到 cur 末尾。
追加后当前层片段 cur="uevoli"。栈不变,继续往右扫下一个字符。
读到第 10 个字符 ) :这一层括号结束。先把当前层片段 cur="uevoli" 原地反转。
把这一层片段反转:"uevoli" 变成 "iloveu"。这一层翻好后,内层早翻好的内容会被再翻一次,正好得到最终顺序。
弹出栈顶的上一层片段 "空",把它接在反转后片段前面,合并成新的 cur="iloveu"。这一对括号结算完毕,回到上一层继续。
整个串扫完,栈已清空,cur="iloveu" 就是最终答案。每对括号都在遇到对应 ) 的那一刻、按从内到外的顺序被反转并拼回,只扫了一遍。
无括号时退化为原样输出;空括号产出空串;嵌套时里层内容会被外层再翻一次,正好对应「从内到外」逐层结算。
两个高频追问:为何栈天然契合嵌套结构,以及存在不产生中间片段的进阶 O(n) 写法。
参考代码
class Solution: def reverseParentheses(self, s: str) -> str: stack = [] cur = [] for ch in s: if ch == '(': stack.append(cur) cur = [] elif ch == ')': cur.reverse() cur = stack.pop() + cur else: cur.append(ch) return ''.join(cur)复杂度
- 时间：O(n²) 最坏，本栈法每遇 ) 都反转并复制 cur;深层嵌套时同一字符会被多层反复反转复制,最坏到平方级
- 空间：O(n)，栈与 cur 合计最多存下整个串的字符
- 可优 O(n)：配对跳转，先记录每个括号的配对位置,再遍历时遇括号就跳到配对处并翻转前进方向,不真正反转任何片段,严格线性
易错点
面试追问把动画讲成自己的话
追问为什么用栈,而不是每遇到一对括号就把子串切出来单独反转?
追问这题还有没有更优的解法?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删除字符串中的所有相邻重复项 II
LeetCode 1209 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题