LeetCode 刷题笔记：1047. 删除字符串中的所有相邻重复项

这道题的核心是“连续相同字符成对消除”，它完全符合栈的思想：如果当前字符和栈顶相同，就删掉它；否则把它压入栈中。

题目要求删除所有相邻重复项后得到最终字符串，直到无法继续删除为止。

题目思路

可以把字符串看成一个动态的结果栈：

  • 遍历原字符串中的每个字符。
  • 如果当前字符和栈顶相同，说明找到了相邻重复对，弹出栈顶，等价于删除这两个字符。
  • 如果不同，则把当前字符压入栈中。

遍历结束后，栈内保存的就是没有相邻重复的结果，但顺序是从底到顶，因此最终需要把栈中的字符反向拼接成答案。

方法 1：显式使用 stack<char>

这种实现最直观，逻辑清晰：

  • 用 stack<char> 存储当前结果字符。
  • 遇到重复字符时直接 pop()。
  • 最后把栈中字符依次弹出并反转。
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        for (auto c : s) {
            if (st.empty() || c != st.top()) st.push(c);
            else st.pop();
        }

        string res;
        while (!st.empty()) {
            res += st.top();
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

优点

  • 语义清楚，直接体现“栈”的匹配思想。
  • 边遍历边删除，时间复杂度 O(n)。

缺点

  • 需要额外反转结果字符串。

方法 2：直接在字符串上模拟栈

这个方法更省空间，也更符合 C++ 常见写法。

  • 使用 string res 作为“栈底到栈顶”的结果容器。
  • res.back() 相当于栈顶元素。
  • 遇到重复则 pop_back()，否则 push_back()。
class Solution {
public:
    string removeDuplicates(string s) {
        string res;
        for (auto c : s) {
            if (res.empty() || res.back() != c) {
                res.push_back(c);
            } else {
                res.pop_back();
            }
        }
        return res;
    }
};

优点

  • 省去了显式 stack<char> 和结果反转。
  • 仍然是 O(n) 时间、O(n) 空间。

关键点总结

  • 这题的本质是“相邻重复对消除”，可以用栈来模拟这个过程。
  • res.empty() 或 st.empty() 检查必须先做，避免访问空栈/空字符串末尾。
  • 这类题目适合把 栈 作为“上一步结果记录器”，当前字符是否与上一个结果匹配决定是否删除。

总结

1047 是一道很好用来练习栈思想的题。
两种方法都能快速通过：一种更直观，适合理解；另一种更简洁，常用于面试和实际编码。
如果你想进一步优化，可以继续思考：是否可以在遍历时直接构造结果字符串，而不需要额外反转，这正是方法 2 所做的。