本文深入剖析 rremove 函数的渐进时间复杂度，指出其实际为 O(n)，而非常见的误判 O(n²)，并通过代码逻辑拆解、迭代次数证明与关键反例说明为何单轮 solve 即可消除所有相邻重复组。
本文深入剖析 `rremove` 函数的渐进时间复杂度，指出其实际为 o(n)，而非常见的误判 o(n²)，并通过代码逻辑拆解、迭代次数证明与关键反例说明为何单轮 `solve` 即可消除所有相邻重复组。
该问题实现了一个“反复移除所有相邻重复字符直至无可移除”的功能（例如 "aabccba" → "ba" → "ba"，终止）。表面上看，外层 while 循环似乎可能执行多次，引发对 O(n²) 的担忧；但核心洞察在于：solve 方法本身已具备全局去重能力——它并非仅删除一对相邻重复，而是对输入字符串进行一次完整扫描，合并并跳过所有连续相同字符段，仅保留每段的首个字符（若未被完全抵消）。
我们来逐层解析：
✅ solve 方法的真实行为
String solve(String s) {
StringBuilder ans = new StringBuilder();
int i = 0;
while (i < s.length()) {
// 若当前字符与下一个相同，跳过整个连续重复段（如 "aaaa" → 跳过全部4个）
if (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
while (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
i++; // 移动至该重复段末尾
}
} else {
ans.append(s.charAt(i)); // 仅保留该段首字符（即“未被抵消”的字符）
}
i++; // 跳过当前处理位置（注意：此处 i++ 在 if-else 外，确保不重复处理）
}
return ans.toString();
}⚠️ 关键点：solve("aabbcc") 直接返回 ""（全抵消），solve("abccba") 返回 "abba"，solve("abccba") 再次调用仍返回 "abba" —— 但更重要的是：solve 从不保留任何相邻重复对。它在单次线性扫描中，对每个连续字符块（run）只决定是否保留 一个 字符（取决于该块长度是否为奇数），且自动跳过偶数长度块（全部抵消）、保留奇数长度块的最后一个字符（等价于首字符经奇偶次抵消后剩余）。
? 示例验证：
s = "aaabbbcc"
- aaa → 长度3（奇）→ 保留 'a'
- bbb → 长度3（奇）→ 保留 'b'
- cc → 长度2（偶）→ 不保留
→ solve(s) = "ab"，无相邻重复。
后续调用 solve("ab") 仍得 "ab"，循环终止。
✅ 外层循环最多执行 1 次
rremove 中的循环条件是：
while (s1.length() != s.length()) {
s1 = s;
s = solve(s);
}由于 solve(s) 总是输出一个不含任何相邻重复字符的字符串（由其逻辑保证），因此：
- 若 s 初始不含相邻重复 → solve(s) == s → 循环零次；
- 若 s 初始含相邻重复 → solve(s) 输出一个更短的、绝对无相邻重复的字符串 s' → 下一轮 solve(s') == s' → 循环恰好执行 1 次后终止。
✅ 因此，solve 最多被调用 2 次（初始 + 一次处理），而每次 solve 是严格 O(n) 时间（单次遍历，每个字符访问常数次）。
⚠️ 为什么有人误判为 O(n²)？
常见误解源于将本算法与「每次仅删除最左一对相邻重复」的暴力模拟（如 "aabbc" → "bbc" → "c"）混淆。后者确实可能触发 O(n) 轮、每轮 O(n) 扫描，导致 O(n²)。但本题 solve 是批量、贪心式压缩：它不模拟“逐步消除”，而是通过指针跳跃直接合成结果，本质是运行长度编码（RLE）的变体。
✅ 时间复杂度结论
- 单次 solve: O(|s|)，线性扫描，无嵌套循环影响整体阶数；
- rremove 调用 solve 至多 2 次 → 总时间复杂度为 O(n)，其中 n 为输入字符串初始长度。
? 补充提醒：虽然时间复杂度为 O(n)，但因 String 不可变及 StringBuilder 的内存分配，空间复杂度为 O(n)；若需极致优化，可改用字符数组原地处理（但逻辑复杂度上升）。
综上，正确理解 solve 的“全量压缩”语义，是避免复杂度误判的关键。
