LeetCode 1047. 删除字符串中的所有相邻重复项
题目描述
题意分析
每次删除一对相邻且相同的字符，删除后其左右两侧会重新相邻，可能继续触发删除。要一直处理到不存在这样的字符对，返回最终字符串，而不是只删除原串中最初相邻的重复项。
这里需要区分两种输入约定：官方题目使用字符串输入和返回值，没有要求原地修改；上方题面图额外写了“原地、O(1) 额外空间”。Java 的
String和 Go 的string都不能原地改写，普通字符串接口使用字符缓冲区需要O(n)空间。若输入本来就是可写字符数组，则可以复用原数组，并返回有效结果长度，满足原地的空间要求。
解法：栈模拟相邻抵消
核心思路
[!blue]
从左到右读取字符，栈始终保存“已读前缀完成全部抵消后的结果”。这份结果内部没有相邻重复项，因此加入新字符时，唯一可能出现的新重复对就是栈顶与当前字符。
如果二者相同，就弹出栈顶，同时丢弃当前字符，正好删除一对；如果不同，或栈为空，就把当前字符追加到栈顶。这样处理后，栈内仍然没有相邻重复项，不变量继续成立。
相同分支只需要一次判断，不需要拿当前字符反复弹栈：当前字符已经与栈顶一起被删除，没有机会再与下一个栈顶匹配。删除后留下的栈本来就是合法前缀，后续读入的字符会继续与新的栈顶比较，从而自然完成连锁消除。
Java 使用
StringBuilder，Go 使用字节切片，直接把缓冲区末尾作为栈顶。最终答案从栈底到栈顶已按原顺序存放，不需要反转，也不需要从原字符串中间反复删除和搬移后缀。
解题步骤
- 创建空字符缓冲区，作为保存已化简前缀的栈。
- 从左到右读入当前字符，先确认栈是否非空。
- 栈顶与当前字符相同时，弹出栈顶，当前字符不入栈。
- 否则将当前字符追加到栈顶。
- 扫描结束后，直接把缓冲区转换为字符串返回。
代码实现
class Solution {
public String removeDuplicates(String s) {
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int top = stack.length() - 1;
// 栈内前缀已完成消除，新字符只需与当前栈顶比较。
if (top >= 0 && stack.charAt(top) == ch) {
stack.deleteCharAt(top);
} else {
stack.append(ch);
}
}
return stack.toString();
}
}
func removeDuplicates(s string) string {
stack := make([]byte, 0, len(s))
for i := 0; i < len(s); i++ {
// 栈内前缀已完成消除，新字符只需与当前栈顶比较。
if len(stack) > 0 && stack[len(stack)-1] == s[i] {
stack = stack[:len(stack)-1]
} else {
stack = append(stack, s[i])
}
}
return string(stack)
}
复杂度分析
- 时间复杂度：
O(n)。每个字符只读一次，至多入栈、出栈各一次；删除缓冲区末尾不需要移动其他字符。- 空间复杂度：
O(n)。如果没有任何字符抵消，缓冲区需要保留整个字符串。
关键点总结
[!green]
- 栈保存的是已读前缀的最终结果，栈顶才是当前字符真正的左邻居。
- 匹配时两个字符同时消失，当前字符不能再参与本轮比较。
- 普通字符串接口需要独立的可写缓冲区，不能把这份空间说成常数。
补充解法：可变字符数组原地消除
核心思路
[!blue]
当输入是可写的
char[]或[]byte时，不再创建另一份栈，而是把原数组前缀当作栈。用read指向下一个待读字符，用size表示栈中有效字符数量，答案始终放在区间[0, size)，栈顶就是chars[size - 1]。先保存
chars[read]。若它与栈顶相同，将size减一，等价于弹栈；否则把它写到chars[size]，再将size加一，等价于入栈。不需要清空被删除的槽位，因为size之外的内容已经不属于有效结果。每轮开始时都有
size <= read：读过的字符不可能留下更多结果。因此写入位置只会是当前读取位置或它左边，绝不会覆盖尚未读取的后缀。每轮保存当前字符后再改写前缀，能够安全复用同一数组。返回
size后，调用方读取原数组的前size个字符即可。下面的接口用于可变数组这一补充要求；若为了适配官方字符串接口而先复制成数组、最后构造字符串，整体仍然需要O(n)空间。
解题步骤
- 将有效长度
size初始化为零。- 用
read顺序读取原数组，并保存当前字符。- 若有效前缀非空且末尾字符相同，将
size减一。- 否则把当前字符写入下标
size，再增加有效长度。- 返回
size，结果保存在原数组的[0, size)区间。
代码实现
class Solution {
public int removeDuplicates(char[] chars) {
int size = 0;
for (int read = 0; read < chars.length; read++) {
char ch = chars[read];
if (size > 0 && chars[size - 1] == ch) {
size--;
} else {
chars[size] = ch;
size++;
}
}
return size;
}
}
func removeDuplicates(chars []byte) int {
size := 0
for read := 0; read < len(chars); read++ {
ch := chars[read]
if size > 0 && chars[size-1] == ch {
size--
} else {
chars[size] = ch
size++
}
}
return size
}
复杂度分析
- 时间复杂度：
O(n)。每个输入字符读取一次，每轮只调整有效长度或写入一个位置。- 空间复杂度：
O(1)。输入已经是可写数组时，只额外保存读指针、有效长度和当前字符，输出也保留在原数组中。
关键点总结
[!green]
- 原地写入成立的原因是有效长度始终不超过已读取长度，写指针不会追上未读区间。
- 删除只需缩短有效前缀，不需要搬动后缀或清理残留字符。
- 返回有效长度保留了原地约定；额外创建结果字符串的内存不属于这个数组接口。
易错点总结
[!yellow]
- 只跳过原串中的相邻对：删除会改变相邻关系，应与化简后前缀的末尾比较。
- 未检查空栈就访问末尾：前面的字符可能已经全部抵消，下一轮必须重新检查长度。
- 弹栈后又把当前字符入栈：相同分支需要删除两个字符，不能把其中一个放回去。
- 按出栈顺序拼接结果：答案已经正向保存在缓冲区中，倒着取会颠倒字符顺序。
- 把转数组后的做法写成整体
O(1)空间：从不可变字符串创建数组本身就需要O(n)，只有调用方已经提供可写数组时才是原地处理。- 原地处理后返回整段旧数组：只有有效长度之前的前缀属于答案，后面的残留值应当忽略。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1209. 删除字符串中的所有相邻重复项 II | 中等 | 从删除两个相邻相同字符推广为删除k个，栈中需要同时保存字符与连续次数。 |
| 2390. 从字符串中移除星号 | 中等 | 同样用栈记录尚未消除的前缀，原题由星号触发，本题由相邻相同字符触发。 |