栈与队列简单1 种解法
#1047删除字符串中的所有相邻重复项
反复删除相邻且相同的两个字符,返回最终稳定字符串。
#字符串#栈
解题主线
01
当前字符等于栈顶时,两者互相抵消;否则当前字符成为新的栈顶。
解法 1:StringBuilder 字符栈
末尾充当栈顶;相同则删除末字符,不同则追加。
时间复杂度
O(n)
空间复杂度
O(n)
java
final class Solution {
public String removeDuplicates(String s) {
StringBuilder stack = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
char current = s.charAt(i);
int size = stack.length();
if (size > 0 && stack.charAt(size - 1) == current) {
stack.setLength(size - 1);
} else {
stack.append(current);
}
}
return stack.toString();
}
}末尾充当栈顶;相同则删除末字符,不同则追加。
边界与易错点
- 栈不应放在实例字段中,否则同一对象重复调用会受旧状态影响。
- StringBuilder 可直接作为字符栈,避免遗留 Stack 的同步开销和最终逆序。
整理来源
由旧仓库源码复核、去重并整理;展示代码已按 Java 21 语义修正明显问题。
easy/Q1047_removeDuplicates.java