题目描述
题目链接：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;} };
扩展思考
- 保留至少 k 个连续字符（进阶题目 1209. 删除字符串中的所有相邻重复项 II）：每次需检查是否连续出现 k 次才进行删除。
- 并行处理多个相邻项（如三元重复、四元重复）：栈结构可扩展存储计数（当前字符+出现次数）。
总结
栈是处理相邻元素匹配问题的核心数据结构，通过维护“已处理序列”的状态，避免暴力解法中的重复扫描。本题与“有效括号”（LeetCode 20）的实现异曲同工，均通过栈的及时弹出来确保数据的合法性。建议类比练习以下题目：
- 20. 有效的括号
- 1209. 删除字符串中的所有相邻重复项 II
- 678. 有效的括号字符串
思考题：如果将问题改为删除两个以上相邻重复项（如 "aaa" → ""），代码应如何调整？