题目描述
思路解析动画文字版
为什么栈天然对路?因为栈顶永远是「最后一个还留着的字符」,而 * 要删的恰恰就是它。入栈 = 留下,弹栈 = 被星号删掉。
开始前栈是空的。指针会从第 0 位一路扫到末尾,边走边维护这个栈。栈里此刻没有任何字符。
扫到第 0 位是普通字母 "l"。它不是星号,先暂时留下来,把它压进栈里。
"l" 入栈,成为新的栈顶。栈从底到顶现在是 [l]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
扫到第 1 位是普通字母 "e"。它不是星号,先暂时留下来,把它压进栈里。
"e" 入栈,成为新的栈顶。栈从底到顶现在是 [l e]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
扫到第 2 位是普通字母 "e"。它不是星号,先暂时留下来,把它压进栈里。
"e" 入栈,成为新的栈顶。栈从底到顶现在是 [l e e]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
扫到第 3 位是普通字母 "t"。它不是星号,先暂时留下来,把它压进栈里。
"t" 入栈,成为新的栈顶。栈从底到顶现在是 [l e e t]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
扫到第 4 位是星号 *。它要删掉「左边最近、还活着」的字符,也就是当前栈顶 "t"。
把栈顶 "t" 弹出去,星号 * 也随之消失。现在栈从底到顶是 [l e e]。
扫到第 5 位是星号 *。它要删掉「左边最近、还活着」的字符,也就是当前栈顶 "e"。
把栈顶 "e" 弹出去,星号 * 也随之消失。现在栈从底到顶是 [l e]。
扫到第 6 位是普通字母 "c"。它不是星号,先暂时留下来,把它压进栈里。
"c" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
扫到第 7 位是普通字母 "o"。它不是星号,先暂时留下来,把它压进栈里。
"o" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c o]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
扫到第 8 位是普通字母 "d"。它不是星号,先暂时留下来,把它压进栈里。
"d" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c o d]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
扫到第 9 位是星号 *。它要删掉「左边最近、还活着」的字符,也就是当前栈顶 "d"。
把栈顶 "d" 弹出去,星号 * 也随之消失。现在栈从底到顶是 [l e c o]。
扫到第 10 位是普通字母 "e"。它不是星号,先暂时留下来,把它压进栈里。
"e" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c o e]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
整串扫完。栈里从底到顶依次是 [l e c o e],拼起来就是答案 "lecoe"。每个字符只入栈或出栈一次,所以是线性时间。
边界:无星号原样返回、可能被删空、单字符也成立。
两个高频追问:用写指针代替显式栈,以及为什么字符串本身就能当栈用。
参考代码
class Solution: def removeStars(self, s: str) -> str: st = [] for ch in s: if ch == '*': st.pop() else: st.append(ch) return ''.join(st)复杂度
- 时间：O(n)，n 是字符串长度,每个字符只被入栈或出栈一次,各做一次常数操作
- 空间：O(n)，最坏情况(没有星号)所有字符都进栈,栈的大小最多到 n
易错点
面试追问把动画讲成自己的话
追问不用栈能做吗?
追问C++ 里为什么能直接拿 string 当栈?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长有效括号
LeetCode 32 · 困难 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题