当前位置：首页 > article >正文

LeetCode刷题实战：删除字符串中的所有相邻重复项（栈的经典应用）

article 2025/3/10 3:52:56

题目描述

题目链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

给定一个由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字符并删除它们。此操作反复进行，直到无法继续删除。返回最终的字符串。答案保证唯一。

输入：s = "abbaca"
输出："ca"
解释：删除 "bb" 得到 "aaca"，再删除 "aa" 得到 "ca"。

问题分析与解法思路

暴力解法的缺陷

最直观的暴力解法是重复扫描字符串，每次删除相邻重复项，直到没有可删项。例如：

第一次扫描找到所有相邻重复对并删除，生成新字符串。
对新字符串重复上述操作，直至不能再删。

这种方法的时间复杂度为 O(n²)（例如形如 aaaaa 的字符串需要进行 n/2 轮扫描），效率极低。显然需要更高效的实现。

栈的核心思想

栈的先进后出（FILO）特性非常适合处理相邻重复项的匹配问题。我们可以用栈存储未处理字符，每次遍历字符时比较当前字符与栈顶元素：

如果相同，则弹出栈顶元素（表示删除这两个相邻重复项）。
否则，将当前字符压入栈。

栈操作完成后，剩余元素即为删除所有相邻重复项后的结果。

为什么栈能解决问题？

栈中存储的元素已经是“处理过的无相邻重复项”的子序列。当遇到一个新的字符时，只需检查它与栈顶是否相同：

相同，弹出栈顶，相当于删除当前字符与栈顶字符的相邻重复对。
不同，压入栈作为新的待匹配字符。

代码实现与逐行解析

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st; // 辅助栈存储未处理字符
        for (char ch : s) { // 遍历每个字符
            if (st.empty() || ch != st.top()) {
                st.push(ch); // 字符入栈：无相邻重复项
            } else {
                st.pop();    // 弹出栈顶：遇到相邻重复项，删除
            }
        }
        string result = "";
        while (!st.empty()) { // 合并栈中剩余字符
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end()); // 反转以恢复原顺序
        return result;
    }
};

步骤解析

初始化栈（第5行）：用于存储需保留的字符。
遍历字符（第6行）：逐个检查每个字符与栈顶的关系。
- 压栈条件（第7行）：栈空或当前字符不等于栈顶。
- 弹栈条件（第9行）：当前字符等于栈顶，删除这一对字符。
构建结果字符串（第12-15行）：栈中剩余字符即为最终字符，但顺序是逆序的（出栈为从尾到头），需反转一次。

关键点说明

时间复杂度 O(n): 每个字符仅出入栈一次，反转操作也是 O(n)。
空间复杂度 O(n): 最坏情况下栈存储全部字符（如无重复项的字符串）。
反转的必要性: 栈的弹出顺序与原字符串顺序相反（例如输入 "abc"，栈弹出顺序为 cba，需反转），确保结果的正确性。

示例分析与测试验证

示例1：输入 s = "abbaca"

遍历过程：
a → 栈空 → 压入 → 栈: [a]
b → 栈顶为a → 压入 → 栈: [a, b]
b → 栈顶为b → 弹出 → 栈: [a]
a → 栈顶为a → 弹出 → 栈: []
c → 栈空 → 压入 → 栈: [c]
a → 栈顶为c → 压入 → 栈: [c, a]

剩余字符：c, a → 反转后结果："ca"

边界测试用例

输入空字符串: 返回空字符串。
输入无相邻重复字符（如 "abcd"）: 结果与原字符串一致。
全部重复字符（如 "aaaaa"）: 最终栈为空，返回空字符串。
嵌套重复项（如 "abba"）: 处理后成为空字符串。

优化与扩展

改进点

直接构建字符串模拟栈：使用 stack 可能需要较多内存操作，可用 string 直接作为栈（以下为优化代码示例）：

class Solution {
public:
    string removeDuplicates(string s) {
        string st; // string模拟栈
        for (char ch : s) {
            if (!st.empty() && ch == st.back()) {
                st.pop_back();
            } else {
                st.push_back(ch);
            }
        }
        return st;
    }
};