题目描述
思路解析动画文字版
一句话套路:把「连续多少个」记在栈顶,凑满 k 就弹掉。弹掉后下一个字符自然去和新的栈顶比较,新相邻关系被自动处理。
上方是输入串 s="abbbaaca",下方是空的计数栈。我们从最左边的字符开始,一个一个往栈里送。
读到第 0 个字符 a,栈为空,它要作为新的一段压入栈。
a×1 压入栈顶。目前栈里拼起来是 "a",这就是「到此为止删不动的结果」。
读到第 1 个字符 b,和栈顶 a 不同,它要作为新的一段压入栈。
b×1 压入栈顶。目前栈里拼起来是 "ab",这就是「到此为止删不动的结果」。
读到第 2 个字符 b,它和栈顶的 b×1 是同一个字符,把栈顶的连续次数加一。
b 现在连续 2 个,还没到 k=3,先留在栈里继续等后面的 b。
读到第 3 个字符 b,它和栈顶的 b×2 是同一个字符,把栈顶的连续次数加一。
b 的连续次数达到 k=3,这一整段 b×3 被删除(弹出栈)。注意:删掉后,新的栈顶又要和后面的字符重新较量。
删除后,栈顶换成了下面那段 a×1。接下来的字符会去和这个新栈顶比较,被删段左右的字符就这样有机会接到一起。
读到第 4 个字符 a,它和栈顶的 a×1 是同一个字符,把栈顶的连续次数加一。
a 现在连续 2 个,还没到 k=3,先留在栈里继续等后面的 a。
读到第 5 个字符 a,它和栈顶的 a×2 是同一个字符,把栈顶的连续次数加一。
a 的连续次数达到 k=3,这一整段 a×3 被删除(弹出栈)。注意:删掉后,新的栈顶又要和后面的字符重新较量。
这一弹之后栈空了,后面的字符将作为全新的一段重新压入。
读到第 6 个字符 c,栈为空,它要作为新的一段压入栈。
c×1 压入栈顶。目前栈里拼起来是 "c",这就是「到此为止删不动的结果」。
读到第 7 个字符 a,和栈顶 c 不同,它要作为新的一段压入栈。
a×1 压入栈顶。目前栈里拼起来是 "ca",这就是「到此为止删不动的结果」。
所有字符扫完。把栈里剩下的每段「字符 ×次数」依次拼起来,就是最终答案 "ca"。中间 bbb 删掉后,左右的 a 接到一起也凑满 3 被删,这正是计数栈自动处理新相邻的威力。
没有相邻相同则原样返回;能整除则可能删空;除不尽时会剩下零头。
两个高频追问:从 k=2 到一般 k 的升级点,以及连环删除为何不用重扫。
参考代码
class Solution: def removeDuplicates(self, s: str, k: int) -> str: stack = [] for ch in s: if stack and stack[-1][0] == ch: stack[-1][1] += 1 if stack[-1][1] == k: stack.pop() else: stack.append([ch, 1]) return ''.join(ch * cnt for ch, cnt in stack)复杂度
- 时间：O(n)，每个字符入栈、出栈各最多一次,一遍扫描
- 空间：O(n)，最坏没有任何删除,栈里要存下所有字符段
易错点
面试追问把动画讲成自己的话
追问和简化版「k=2 删相邻重复项」相比,这题难在哪?
追问为什么计数栈能保证连环删除都被处理到?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
移除无效的括号
LeetCode 1249 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题