题目描述
思路解析动画文字版
记住:新值能压倒的栈顶都得移除(它右边有更大的),压不倒就停、把自己压栈。下面逐帧套它。
遍历链表:读到第 1 个节点(值 5),抄进数组 vals 的下标 0。
遍历链表:读到第 2 个节点(值 2),抄进数组 vals 的下标 1。
遍历链表:读到第 3 个节点(值 13),抄进数组 vals 的下标 2。
遍历链表:读到第 4 个节点(值 3),抄进数组 vals 的下标 3。
遍历链表:读到第 5 个节点(值 8),抄进数组 vals 的下标 4。链表读完,vals 已就绪,下面切到数组上跑单调栈。
vals 抄好了:柱子高度 = 节点值,柱子下方数字 = 下标。从左到右扫一遍,空栈起步,栈里维护「目前还该保留」的下标。
轮到下标 0(高 5,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
栈已空,没有可移除的。把当前下标 0 压栈(暂时保留它),继续往右扫。此刻保留栈 = [0],已移除 = [无]。
轮到下标 1(高 2,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
栈顶下标 0(高 5)不比 2 矮(5 ≥ 2),停止弹出。把当前下标 1 压栈(暂时保留它),继续往右扫。此刻保留栈 = [0, 1],已移除 = [无]。
轮到下标 2(高 13,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
栈顶是下标 1(高 2,标红),它严格小于当前的 13,说明 1 号节点右边冒出了更大的 13,1 号(值 2)必须移除,从栈里弹出。
栈顶是下标 0(高 5,标红),它严格小于当前的 13,说明 0 号节点右边冒出了更大的 13,0 号(值 5)必须移除,从栈里弹出。
栈已空,没有可移除的。把当前下标 2 压栈(暂时保留它),继续往右扫。此刻保留栈 = [2],已移除 = [0, 1]。
轮到下标 3(高 3,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
栈顶下标 2(高 13)不比 3 矮(13 ≥ 3),停止弹出。把当前下标 3 压栈(暂时保留它),继续往右扫。此刻保留栈 = [2, 3],已移除 = [0, 1]。
轮到下标 4(高 8,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
栈顶是下标 3(高 3,标红),它严格小于当前的 8,说明 3 号节点右边冒出了更大的 8,3 号(值 3)必须移除,从栈里弹出。
栈顶下标 2(高 13)不比 8 矮(13 ≥ 8),停止弹出。把当前下标 4 压栈(暂时保留它),继续往右扫。此刻保留栈 = [2, 4],已移除 = [0, 1, 3]。
扫完整条数组。保留栈里是下标 2, 4(蓝色,值 13、8),高度从栈底到栈顶不增;灰色的下标 0、1、3 都因为右边有更大值被移除了。保留的就是答案。
把结论映射回原链表:下标 0、1、3(值 5、2、3)被移除(灰),它们右边都存在更大的节点。
把保留的节点按原顺序接起来,就是结果链表 13→8。回头看:我们只把链表抄了一遍、又扫了一遍数组,每个下标进栈出栈各一次,O(n) 就定出了该留谁。
边界:递增只剩尾、不增(含相等)全留、空与单节点原样。
面试常考:进出栈各一次所以 O(n);反转+前缀最大与单调栈等价。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]: def rev(node): prev = None while node: nxt = node.next node.next = prev prev = node node = nxt return prev head = rev(head) dummy = ListNode(0) tail = dummy best = -10**18 cur = head while cur: nxt = cur.next if cur.val >= best: best = cur.val tail.next = cur tail = cur cur = nxt tail.next = None return rev(dummy.next)复杂度
- 时间：O(n)，单调栈视角:每个下标进栈一次、出栈一次,均摊线性。等价代码:两次反转 + 一次遍历,也是 O(n)
- 空间：O(n)，单调栈最坏(整体不增时)装下全部节点。等价代码原地反转是 O(1) 额外空间,这里按单调栈口径记 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么单调栈能一遍就定出保留谁?
追问反转法和单调栈是什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
K 个一组翻转链表
LeetCode 25 · 困难 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题