1047. 删除字符串中的所有相邻重复项：不是模拟！而是利用 LIFO（栈或双指针模拟栈的确定下推自动机）.md

题目简述：

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

题目链接：1047. 删除字符串中的所有相邻重复项

最初思路：模拟（超时）

思路是以 '@' 占位以表示逻辑删除，然后按题目描述地不断进行两两删除。

这样实现的算法最终能够解出正确答案，但是在力扣的某个测试用例上超时（1 <= s.length <= 10^5）。算法的时间复杂度为 $O(n^2)$。

class Solution {

    private char[] ss;
    private int n;

    public String removeDuplicates(String s) {
        ss = s.toCharArray();
        n = ss.length;

        while (removeNeighbour()) ;
        StringBuilder sb = new StringBuilder();
        for (char c : ss) {
            if (c != '@') sb.append(c);
        }
        return sb.toString();
    }

    // 以 '@' 占位表示逻辑删除，返回 true 表示成功删除
    private boolean removeNeighbour() {
        int prev;
        for (prev = 0; prev < n - 1; prev++) {
            if (ss[prev] != '@') break;
        }

        int i = prev + 1;
        while (i < n) {
            if (ss[i] == '@') {
                i++;
            } else if (ss[i] != ss[prev]) {
                prev = i;
                i++;
            } else {
                ss[prev] = '@';
                ss[i] = '@';
                return true;
            }
        }

        return false;
    }
}

即使再加上全局变量 start （下一次 removeNeighbour() 循环的起始位置）以尽可能减少从头开始遍历搜索的次数，依然会超时。

改进算法：“中心扩展”

回顾模拟的算法，发现问题在于当前设计很难高效找出下一次 removeNeighbour() 循环的起始位置，即使使用 start 变量存储上上次扫描的字符索引，也会遇到由于信息缺失而不得不赋 start 为 0 的情况。

再度观察问题，发现似乎有高效的解决方案：由于每次删除只能删除逻辑上未删除的相邻元素，因此我们可以考虑 “中心扩展” 的算法。例如 "...abccbd..."，我们首先从直接相邻的 "cc" 入手，删除 "cc" 后考察 "cc" 左右的元素，发现分别为 'b' 与 'b'，是相同元素，因此继续删除，接着再考察两个 'b' 左右的元素，发现分别为 'a' 与 'd'，系不同元素，无法删除，于是我们继续考察 'd' 及其后面的元素……

根据我们的逻辑，我们需要维护一个 prev 指针，用于向前寻找上一个未删除元素。这样，我们就可以保证当前扫描的元素其右侧的元素必然未删除，只需要向左回退并对比 prev 的值与右侧元素的值是否相同。或许符合确定下推自动机模型？

其实应该是一个用栈的确定下推自动机（PDA）

这样算法的时间复杂度为 $O(n)$，因为 prev 的回退当且仅当在删除相邻元素时发生，且前提是 prev 的值合法（未越界）。空间复杂度为 $O(1)$。以下是 GPT-5 给的时间复杂度证明：

定义势能（Potential） $$ \varPhi = \text{当前未被删除的字符数} = \text{栈大小} $$ 逐字符处理 i = 0..n-1：

• 压栈（未匹配）：实际代价 $c=1$（一次比较 + 赋值）；势能变化 $\Delta\Phi=+1$。 摊还代价 $\hat c = c + \Delta\Phi = 2$。
• 配对删除（匹配）：一次删除可能连锁（级联）多次，但每成功删除一对，实际代价按常数计 $c=1$，势能 $\Delta\Phi=-1$。 摊还代价 $\hat c = c + \Delta\Phi = 0$（甚至为非正）。

把整段处理求和：

• 每个字符至多一次走“压栈”分支（$\hat c\leqslant2$）。
• 每次删除对的摊还代价非正，总和不会变大。

于是总摊还代价 $\sum \hat c\leqslant2n$，故总实际代价 $\sum c\leqslant2n$，即 $\boldsymbol{O(n)}$。

备注：你实现里在删除后通过 do { prev--; } while (ss[prev]=='@') 连续左退跨过若干墓碑（'@'），这些移动可以计入该次删除的常数成本，因为每退一格都对应一个此前已完成的“弹栈”（势能已降低），对总摊还成本不利的贡献 ≤ 0，不会破坏 $O(n)$ 结论。

该算法实现 AC 时时间开销优于力扣上 95% 的 AC 代码。

class Solution {
    public String removeDuplicates(String s) {
        int n = s.length();
        char[] ss = s.toCharArray();
        int prev = -1;  // 上一个未删除元素的位置

        int i = 0;
        while (i < n - 1) {
            
            if (ss[i] == ss[i + 1]) {
                ss[i] = '@';
                ss[i + 1] = '@';

                i += 2;
                while (i < n) {
                    if (prev == -1 || ss[prev] != ss[i]) {
                        break;
                    } else {
                        ss[prev] = '@';
                        ss[i] = '@';
                        i++;
                        do {
                            prev--;
                        } while (prev >= 0 && ss[prev] == '@');
                    }
                }
            } else {
                prev = i;
                i++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : ss) {
            if (c != '@') sb.append(c);
        }
        return sb.toString();
    }
}

显式数据结构：用栈简化逻辑

此前我实现的 “中心扩展” 方案，实际上完全等价于用双指针的方式模拟了栈的行为。因此，本问题完全可以显式地用栈解决。

其实仔细想来，可能我的确将问题复杂化了。这个问题的性质使得他的确很适合栈这一 LIFO 性质的数据结构……因为存在 “匹配” 的性质。想想括号匹配，和这里一样，都是两两匹配的问题。嗯……为什么我一开始没想到、而是想着去模拟呢？

对于 Java，StringBuilder 本身就可以当作栈使用。

算法的时间复杂度也为 $O(n)$。

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (sb.length() == 0 || sb.charAt(sb.length() - 1) != c) {
                sb.append(c);
            } else {
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return sb.toString();
    }
}