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

问题描述

给定一个字符串 s，需要重复地删除其中所有相邻的重复项，直到没有任何相邻字符是重复的。最后返回处理后的字符串。

示例

• 示例 1:

  • 输入: abbaca
  • 输出: ca
  • 解释: 先删除 bb（得到 aaca），然后删除 aa（得到 ca）。

• 示例 2:

  • 输入: abbbabaa
  • 输出: ab 或 ba
  • 解释: 删除可能有不同的顺序，比如先删除第一个 bb 再删除第二个 bb 得到 abaa，然后再删除 aa 得到 ab。

class Solution {
    public String removeDuplicates(String S) {
        StringBuffer stack = new StringBuffer();
        int top = -1;
        for (int i = 0; i < S.length(); ++i) {
            char ch = S.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                stack.deleteCharAt(top);
                --top;
            } else {
                stack.append(ch);
                ++top;
            }
        }
        return stack.toString();
    }
}

• 用 StringBuffer 作为栈：

  • StringBuffer 用于存储字符，模拟栈的行为。
  • 变量 top 用来追踪栈顶位置。

• 遍历字符串 S：

  • 对于每个字符 ch，检查与栈顶字符是否相同。

• 栈操作：

  • 如果栈不为空（top >= 0）且栈顶字符与当前字符相同，则删除栈顶字符，并更新栈顶位置 top。
  • 否则，将当前字符添加到 stack 中，并更新栈顶位置 top。

• 返回结果：

  • 将 StringBuffer 转换为字符串并返回。

优点

• 空间效率：直接使用 StringBuffer 而不是标准栈结构，减少了空间开销。
• 时间效率：由于 StringBuffer 的内部实现优化，这种方法比标准栈操作更快。
• 简洁性：代码简洁明了，易于理解。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度。每个字符被处理一次。
• 空间复杂度：O(n)，最坏情况下，StringBuffer 中可能需要存储所有字符。

可能有疑问

为什么 如果栈不为空就是top >= 0

变量 top 被用来追踪 StringBuffer（在这里充当栈的角色）的栈顶位置。这里的逻辑是：

1. 当 stack（StringBuffer 实例）为空时，意味着没有任何元素被添加进去。在这种情况下，top 的值为 -1。这是因为在空的 StringBuffer 中，没有任何字符的索引可以是 0 或更大的数（在Java中，索引通常是从 0 开始的）。因此，-1 被用作表示“栈空”或“没有元素”的标记。

2. 当向 stack 中添加第一个元素时，top 的值从 -1 变为 0，表示现在有一个元素在 stack 中，且这个元素位于索引 0 的位置（也就是栈顶）。

3. 因此，如果 top 的值大于或等于 0，意味着 stack 中至少有一个元素，即 stack 不为空。相反，如果 top 的值仍然是 -1，则意味着 stack 为空。

top >= 0 的条件用来检查 stack 是否不为空，即是否有元素可以进行比较和可能的删除操作。这种使用一个额外的变量来追踪栈顶位置的方法是一种常见的编程技巧，用于在不使用标准栈数据结构的情况下模拟栈的行为。