本文深入剖析“递归移除字符串中所有相邻重复字符”算法的真实时间复杂度，澄清常见误解（如误判为 o(n²)），通过代码逻辑拆解与执行过程模拟，严谨论证其线性时间特性 o(n)，并给出可验证的优化实现。
本文深入剖析“递归移除字符串中所有相邻重复字符”算法的真实时间复杂度，澄清常见误解（如误判为 o(n²)），通过代码逻辑拆解与执行过程模拟，严谨论证其线性时间特性 o(n)，并给出可验证的优化实现。
该问题的核心在于理解 rremove 函数中循环调用 solve 的实际行为——并非每轮仅消除一对相邻重复，而是每轮 solve 会一次性扫描并跳过所有连续重复段，仅保留每个连续段的首个（或零个）字符。因此，整个算法的执行轮数远低于 n，最坏情况下仅为常数轮（例如 "aabbbcc" → "ac"，仅需 2 轮），而非直觉中的“逐对消除、反复扫描”。
我们先看 solve 方法的关键逻辑：
String solve(String s) {
StringBuilder ans = new StringBuilder();
int i = 0;
while (i < s.length()) {
// 发现相邻重复：跳过整个连续重复段（如 "aaaa" → 跳过全部）
if (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
char c = s.charAt(i);
while (i < s.length() - 1 && s.charAt(i) == c && s.charAt(i + 1) == c) {
i++; // 注意：此步仅推进索引，不添加字符
}
i++; // 跳出内层 while 后，再跳过最后一个重复字符（因外层 while 需继续）
} else {
ans.append(s.charAt(i));
i++;
}
}
return ans.toString();
}⚠️ 关键洞察：solve 不是“删除一对后重头扫描”，而是一次性线性扫描完成全局去重——它识别出 "aaabbbcc" 中的 "aaa" 就直接跳过全部三个 'a'，不保留也不追加；同理跳过 "bbb" 和 "cc"，最终只留下空结果（若全为重复段）或孤立字符。因此，单次 solve 的时间复杂度严格为 O(n)，且最多执行常数轮（≤ ⌈log₂n⌉ 轮，在极端链式消除下也远小于 n）。
再看外层循环：
String rremove(String s) {
String s1 = "";
while (s1.length() != s.length()) {
s1 = s;
s = solve(s); // 每轮输入规模严格减小（至少减少 2 个字符，如 "aa"→""）
}
return s;
}由于每次 solve 至少消除一组长度 ≥2 的相邻重复（即 |s| 至少减少 2），总轮数上限为 ⌊n/2⌋，但更紧确界是 O(log n)（类比“每次消除所有偶数位置重复导致指数级缩减”）。然而，所有轮次的 solve 调用总工作量之和仍为 O(n)：因为每轮扫描的字符串长度单调递减，形成等比数列求和（n + n/2 + n/4 + … = 2n）。
✅ 结论：该算法整体时间复杂度为 O(n)，而非 O(n²)。所谓 O(n²) 的误判，源于将 solve 错误理解为“仅删除首对重复后返回”，从而假设需调用 n 次；实际上 solve 是贪心一次扫描的全局简化器。
? 进阶建议：若追求极致效率与空间局部性，可用栈模拟（单次遍历、O(n) 时间 + O(n) 空间），代码更简洁且无循环调用开销：
public String rremove(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek() == c) {
stack.pop(); // 匹配则弹出（相当于消去一对）
} else {
stack.push(c);
}
}
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()) res.append(stack.pollLast());
return res.toString();
}此栈解法不仅时间复杂度明确为 O(n)，且逻辑清晰、易于验证，推荐在工程实践中采用。
