字符串解码

字符串解码这道题在问什么

输入形如 3[ab2[cd]e] 的编码串，规则是 k[内容] 表示把方括号里的内容重复 k 次，且括号可以任意嵌套，要求还原出展开后的字符串。真正的难点只有一个：嵌套。扫到外层的 3[ab 时里面的 2[cd] 还没解开，外层「重复 3 次」这件事必须先记下来、等内层处理完再兑现。

为什么处理嵌套括号自然想到栈

嵌套括号的闭合顺序是后进先出：最晚打开的括号最先闭合，每个右方括号要匹配的都是最近一个还没闭合的左方括号。「最近打开、最先处理」正是栈的定义，所以括号类解析几乎都以栈为骨架。

关键观察是：任何时刻真正需要动手维护的只有两样东西——当前括号层正在收集的串 cur，和正在逐位攒的倍数 k。至于外层「等会儿要重复几次、展开后接在谁后面」，属于暂时用不上的上下文，遇到左方括号时整体压栈冷冻，等对应的右方括号出现再解冻，恰好不多不少。

两个栈各存什么，压栈后为什么要清空

参考代码用两个栈配合：num_st 存各层的倍数，str_st 存进入各层之前已经拼好的前串。扫描规则四条：遇数字按 k = k * 10 + 当前位累积；遇左方括号把 k 和 cur 分别压栈，然后 cur 清空、k 归零；遇字母直接接到 cur 末尾；遇右方括号执行 cur = str_st.pop() + cur * num_st.pop()。

压栈后必须清空，因为括号内部是一段全新的子串，要从零开始收集，旧的 cur 若不清空会把外层内容错误地卷进重复。而右方括号处的拼接方向也不能反：弹出的前串在前、重复好的括号内容在后，这与它们在原串里的先后位置一致。

为什么一遍扫完结果就是对的

整个算法维持着一条不变量：任何时刻 cur 都是「当前最深那层括号内、已扫过部分的完整展开」，而栈里自底向上依次保存着更外层的半成品和倍数。每闭合一层，就把该层的展开乘上倍数、合并回上一层的半成品，不变量重新成立。扫完全串时所有括号都已闭合、两栈为空，cur 自然就是整串的展开结果，不需要任何补处理。

复杂度怎么算，哪些细节容易错

时间 O(maxK · n)：每个字符可能被外层倍数放大若干倍，n 取输出长度的量级；空间 O(n)，两个栈的深度随嵌套层数增长，cur 随输出增长。

两个高频翻车点：一是倍数可能是多位数，12[a] 里的 12 必须用 k = k * 10 + int(c) 累积，按一位数处理直接出错；二是想省掉一个栈行不通，倍数和前串是两类信息，闭合时要同时取回才能还原「重复几次、接到谁后面」。若偏好递归，可以在每个左方括号处递归解码子串，用调用栈替代显式栈，逻辑完全等价。