递归去重相邻字符的正确时间复杂度分析

本文揭秘了一个常被误判为O(n²)实则具备线性时间复杂度O(n)的递归去重算法，关键在于深入剖析`solve`函数并非逐对删除相邻重复字符，而是通过贪心跳过机制单趟扫描即可消除所有连续重复段，并暴露出的新重复关系也在同一轮中一并处理；结合外层循环至多执行一次的有效收敛性，彻底推翻“需多次迭代”的误解，揭示其高效本质——真正理解这种批量坍缩式扫描逻辑，才是准确评估类似字符串处理算法复杂度的核心所在。

本文澄清一个常见误解：对“递归调用 solve 移除所有相邻重复字符”的算法，其真实时间复杂度为线性 O(n)，而非部分资料误判的 O(n²)，关键在于 solve 函数单次即可消除全部相邻重复段，且外层循环最多执行一次。

本文澄清一个常见误解：对“递归调用 `solve` 移除所有相邻重复字符”的算法，其真实时间复杂度为线性 O(n)，而非部分资料误判的 O(n²)，关键在于 `solve` 函数单次即可消除全部相邻重复段，且外层循环最多执行一次。

该问题的核心在于理解 rremove 方法中 while 循环的实际执行次数——它并非按字符数量或轮次线性增长，而是具有强收敛性：至多执行 1 次完整迭代。

我们来逐步分析：

✅ solve 函数：单趟扫描，O(n) 完成全局去重

solve 并非“每次只删一对相邻重复”，而是采用贪心跳过策略：

• 遍历字符串时，一旦发现 s[i] == s[i+1]，就持续向后滑动 i，跳过整个连续重复段（例如 "aaabbbcc" 中的 "aaa" 会被一次性跳过）；
• 仅将每个连续段的首个字符之外的所有字符跳过，而首个字符也不保留（因后续必然与前一不同段分隔），真正追加的是所有非重复起始位的孤立字符；
• 更重要的是：该实现实际完成的是「移除所有长度 ≥ 2 的连续重复子串的首尾重叠部分」，等价于标准的「相邻重复消除」（如 "abbaca" → "ca"）。虽然代码逻辑略隐晦，但效果是：一轮 solve 就能消除所有当前存在的相邻重复对，并可能暴露出新的相邻关系（如 "aabba" → "a"）。

? 示例验证：
输入 "abbbaca"

• 第一趟 solve：
  • i=0: 'a'≠'b' → append 'a'
  • i=1: 'b'=='b' → 跳过 i=1,2（覆盖 "bbb"），i 最终停在 3；接着 i++ 后为 4
  • i=4: 'a'=='a' → 跳过 i=4，i 停在 5；i++ 后为 6
  • i=6: 'c'≠'a' → append 'c'；最后 append 'a'
    → 得 "aca"
• 第二趟 solve("aca")：无相邻重复 → 输出 "aca"，与输入等长 ⇒ 循环终止
  仅调用 2 次 solve，且每次均为 O(n)

✅ 外层 rremove 循环：最多执行 1 次有效迭代

关键观察：

• 字符串长度严格单调递减（除非已无重复，此时 s1.length() == s.length() 立即退出）；
• 每次 solve(s) 至少消除 ≥ 2 个字符（因至少存在一对相邻重复才会进入内层 while）；
• 但更重要的是：不可能出现“消除一部分 → 新重复 → 再消除一部分 → ……反复 n 次”的链式场景。
  实际上，solve 的扫描机制保证了：所有因前序删除而新暴露的相邻字符，会在同一趟扫描中被识别并处理（因其基于原始索引顺序、无回溯，但通过跳过逻辑隐含了“批量坍缩”效果）。形式化证明可借助「势函数」：定义势 Φ(s) = 字符串中相邻相等位置对的数量，则每趟 solve 至少减少 Φ，且 Φ ≤ n−1，故总迭代数 ≤ n；但实践中，由于消除是成块发生的，典型输入下 Φ 快速归零 —— 经验与理论均支持最坏情况仍为 O(1) 次调用。

因此，总时间复杂度 = solve 调用次数 × 单次 solve 复杂度 = O(1) × O(n) = O(n)。

⚠️ 注意事项与常见误区

• ❌ 误区：“solve 每次只删一对，所以要调用 O(n) 轮” → 错。本实现中 solve 是全量扫描器，不是单步消重器；
• ✅ 正确理解：solve 的 while(i < ... && s[i]==s[i+1]) i++ 是跳过整个连续重复块，而非逐对处理；
• ? 优化提示：当前 rremove 使用字符串比较 s1.length() != s.length() 判定收敛，虽简洁，但若需更高鲁棒性，可改用 !s1.equals(s)（避免长度相同但内容不同的巧合）；
• ? 空间复杂度：StringBuilder 为 O(n)，无递归栈，故总空间为 O(n)。

✅ 总结

该算法的时间复杂度确为 O(n)，主因是 solve 函数具备“单趟全局消重”能力，且外层收敛极快。所谓 O(n²) 的判断，源于对 solve 行为的误读（将其当作朴素的一对一删除）。掌握扫描类双指针/跳过式遍历的“批量处理”本质，是准确分析此类问题的关键。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《递归去重相邻字符的正确时间复杂度分析》文章吧，也可关注golang学习网公众号了解相关技术文章。