【Hot 100 刷题计划】 LeetCode 394. 字符串解码 | C++ 单栈回压法
LeetCode 394. 字符串解码
📌 题目描述
题目级别：中等
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为:k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。
示例 1:
输入：s = "3[a]2[bc]"
输出："aaabcbc"示例 2:
输入：s = "3[a2[c]]"
输出："accaccacc"
💡 破题思路：单栈回压法 (Single Stack Re-push)
绝大多数教程在讲这道题时，都会教你使用“双栈法”（一个栈存数字，一个栈存字符串）。
但实际上，仅用一个字符栈也能极其优雅地解决问题，并且逻辑更加贴近底层硬件的工作方式。
本解法完美处理了两个最大痛点：
- 多位数字还原：当遇到
]弹栈找数字时，数字是倒着出来的（比如100，先弹出0，再弹出0，最后弹出1）。我们利用权重变量w（初始为 1，每次乘 10），通过k = (st.top() - '0') * w + k完美还原真实数值。 - 嵌套括号问题 (核心魔法)：当遇到
3[a2[c]]这种嵌套结构时，我们在内部遇到第一个]，解出了cc。此时千万不能把它直接加到最终结果里！我们的做法是：把它打散成字符，重新push回栈里！这样一来，cc就变成了普通的字符，和外层的a紧紧挨在了一起，静静等待外层括号的下一次结算。这就叫“回压法”。
💻 C++ 代码实现 (单栈极客版)
classSolution{public:stringdecodeString(string s){intn=s.size();stack<char>st;// 全局仅需一个字符栈string res;for(inti=0;i<n;i++){if(s[i]!=']'){// 不是右括号，统统入栈保存现场st.push(s[i]);}else{// 遇到右括号，开始清算当前这一层！string tmp;// 1. 弹出中括号内的纯字母字符串while(st.top()!='['){// 注意拼接顺序，栈是先进后出的，所以要加在前面tmp=st.top()+tmp;st.pop();}st.pop();// 弹出 '['// 2. 弹出前面的数字 (支持多位数字解析)intk=0,w=1;while(!st.empty()&&st.top()>='0'&&st.top()<='9'){k=(st.top()-'0')*w+k;w*=10;st.pop();}// 3. 将字符串按照解析出的数字倍数进行放大string add;for(intj=0;j<k;j++){add+=tmp;}// 4. 终极魔法：将放大后的字符串重新逐个压回栈中！// 完美化解嵌套危机，让它们参与外层括号的下一次清算for(intj=0;j<add.size();j++){st.push(add[j]);}}}// 大循环结束后，栈里剩下的就是完全解码的字符了while(st.size()){res=st.top()+res;st.pop();}returnres;}};