[!info] related notes 算法面试题型 MOC 栈

删除字符串中的所有相邻重复项

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

题型判断

这是最典型的“相邻消除”类栈题。

关键信号：

• 当前字符只会和前面最近留下来的字符发生反应
• 消除之后，新的相邻关系可能继续出现

所以用栈维护“消除后剩下的字符串”。

核心思路

• 如果当前字符和栈顶相同，弹栈，表示这两个字符一起消掉
• 否则把当前字符压栈
• 最后把栈里的字符拼起来

为什么这里适合用栈

因为消除之后，新的相邻字符一定出现在“剩余串的末尾”，也就是栈顶附近。

JavaScript

var removeDuplicates = function(s) {
    const stack = [];

    for (const ch of s) {
        if (stack.length && stack[stack.length - 1] === ch) {
            stack.pop();
        } else {
            stack.push(ch);
        }
    }

    return stack.join('');
};

一句话总结

把栈看成“已经处理好的结果串”，当前字符只需要和结果串末尾比较。