题目链接：点击消除 (nowcoder.com)
一、分析题目
⽤栈来模拟消除的过程。
（细节：这里不一定非得用真的栈结构，可以利用可变长的数组（string）来模拟栈）
将第一个元素直接入栈，接着从第二个字符开始往后遍历字符串，将遍历到的字符和栈顶元素进行比较，相同就删去栈顶元素（这一步相当于消消乐），不同就入栈。
- 时间复杂度：O(N)
- 空间复杂度：O(N)
二、代码
1、自己 AC 的代码
//没看题解之前AC的代码 #include <iostream> #include <stack> #include <algorithm> using namespace std; int main() { string s; cin >> s; stack<char> st; for(int i=0; i<s.size(); i++) { if(st.size() && s[i]==st.top()) st.pop(); else st.push(s[i]); } string res; while(st.size()) { res+=st.top(); st.pop(); } reverse(res.begin(), res.end()); if(res.size()==0) cout << 0 << endl; else cout << res << endl; return 0; } //看过题解之后AC的代码 #include <iostream> using namespace std; int main() { string s; cin >> s; string st; for(int i=0; i<s.size(); i++) { if(st.size() && s[i]==st.back()) st.pop_back(); else st+=s[i]; } if(st.size()==0) cout << 0 << endl; else cout << st << endl; return 0; }
2、值得学习的代码
#include <iostream> #include <string> using namespace std; int main() { string s, st; cin >> s; for(auto ch : s) { if(st.size() && st.back() == ch) st.pop_back(); else st += ch; } cout << (st.size() == 0 ? "0" : st) << endl; return 0; }
三、反思与改进
在做这道题目的时候没有联想到要用栈这个数据结构来辅助完成，而是在原字符串上直接操作，这样需要考虑的情况就特别多，代码非常冗余。反而是在交卷之后才想起之前做过类似的 “消消乐” 的题目，就是利用栈的先进后出的特点，说明类似题目做的还是太少了，对栈的掌握也还不够。虽然在清楚了本题所考察的内容后能够不看题解顺利做出，但是代码还是可以进行优化（利用 string 来模拟栈结构），这样做可以避免从栈里取出字符时还要 reverse。
