题目描述
思路解析动画文字版
想从外往里一次替换 3[...] 替不动，因为里面还没解完。必须先存住外层、钻进内层。
用两个栈：数字栈存这层要重复几次，字符串栈存进括号前已经攒好的前缀。
读到 3[ · 保存外层现场：读到左括号，先别拼字符串：把次数 3 和当前前缀压两个栈，再清空 cur 去读里面。
读到 a · 当前串增长：字母 a 不是括号，直接接到当前串后面。这一步两个栈都不动。
读到 2[ · 再保存一层现场：又遇左括号：把次数 2 和此刻前缀 a 压栈，cur 清空。栈越压越深，对应括号越嵌越里。
读到 c · 内层当前串增长：在最里层读到 c，接到当前串上。注意 cur 现在只装着里层攒的 c。
遇到内层 ] · 第一步先弹栈：右括号要拆成两帧看。这一帧只做弹栈：取回最近存的次数 2 和前缀 a。最近进的括号最先恢复，正是栈。
遇到内层 ] · 第二步合成：这一帧合成：前缀 a 接上 c 重复两次，cur 变成 acc。弹栈和拼接拆开两帧，动作才看得清。
遇到外层 ] · 弹 k=3 再重复：最后的外层右括号：弹出次数 3，把 acc 重复三次。栈空了，cur 就是最终答案。
灵魂帧慢放 · 右括号的两步走：这就是全题的核心动作，慢放一遍：每遇右括号，弹出最近的次数和前缀，再用 prev 加 cur 重复 k 次。
左括号按下暂停键把现场压栈，右括号松开暂停键弹栈把内层结果接回去。
雷区实演 · 顺序写反 prev/cur：用同一组数据演一遍坑：拼接顺序写反，acc 就变成 cca，往上层一路传错。前缀永远放前面。
边界三连：多位数字、并列编码、括号前前缀，三种都跑通才算稳。
面试追问 1：数字栈和字符串栈，恢复现场时必须成对弹出，一一对应每个左括号。
面试追问 2：输出可以远大于输入，所以时间和空间都钉在答案长度上。
面试追问 3：递归就是借系统调用栈做同一件事；面试可以两种都聊，思路完全对应。
学完别乱跳，去 栈专题 连刷同类的嵌套结构题；卡住时用 AI 答疑追问『右括号这一步为什么要弹栈』，比死背更稳。
参考代码
class Solution: def decodeString(self, s): nums, strs = [], [] cur, num = '', 0 for ch in s: if ch.isdigit(): num = num * 10 + int(ch) elif ch == '[': nums.append(num) strs.append(cur) cur, num = '', 0 elif ch == ']': k = nums.pop() prev = strs.pop() cur = prev + cur * k else: cur += ch return cur复杂度
- 时间复杂度：O(|ans|)，每个输出字符至少被构造一次；输出多长就要拼多长
- 空间复杂度：O(depth + |ans|)，两栈深度=括号嵌套层数，加上结果串本身
可套用的代码模板
这是可迁移骨架，不是复读答案：换题时先认清『开始符存什么现场、结束符怎么合并』，再填那两个分支。
# 嵌套/括号题判据：遇到『开始符』要不要存现场？遇到『结束符』要不要弹栈合并？num_stack, str_stack = [], []cur, num = '', 0for ch in s: if 是数字: num = num*10 + 值 # 累计本层参数 elif 是开始符: # 进内层 num_stack.append(num) # 存现场 str_stack.append(cur) cur, num = '', 0 # 重置 elif 是结束符: # 出内层 k = num_stack.pop() # 弹现场 cur = str_stack.pop() + cur*k # 合并(前缀在前) else: cur += chreturn cur易错点
面试追问把动画讲成自己的话
追问为什么要用两个栈，不能合成一个？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长有效括号
LeetCode 32 · 困难 · 沿着 栈 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题