题目描述
思路解析动画文字版
记住:栈里存「还在等更大值」的下标,新值能压倒谁就给谁结算、弹出谁。下面逐帧套它。
遍历链表:读到第 1 个节点(值 1),把它抄进数组 vals 的下标 0。
遍历链表:读到第 2 个节点(值 7),把它抄进数组 vals 的下标 1。
遍历链表:读到第 3 个节点(值 5),把它抄进数组 vals 的下标 2。
遍历链表:读到第 4 个节点(值 1),把它抄进数组 vals 的下标 3。
遍历链表:读到第 5 个节点(值 9),把它抄进数组 vals 的下标 4。
遍历链表:读到第 6 个节点(值 2),把它抄进数组 vals 的下标 5。
遍历链表:读到第 7 个节点(值 5),把它抄进数组 vals 的下标 6。
遍历链表:读到第 8 个节点(值 1),把它抄进数组 vals 的下标 7。链表读完,vals 已就绪,下面切到数组上跑单调栈。
vals 抄好了:柱子高度 = 节点值,柱子下方数字 = 下标。现在从左到右扫一遍,空栈起步,栈里只放「还在等更大值」的下标。
轮到下标 0(高 1,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈已空,没有可结算的。把当前下标 0 压栈,让它去等自己的下一个更大值。此刻 ans = [0, 0, 0, 0, 0, 0, 0, 0]。
轮到下标 1(高 7,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈顶是下标 0(高 1,标红),它严格小于当前的 7,说明 7 就是它右边第一个更大值。填 ans[0] = 7,把下标 0 弹出。
栈已空,没有可结算的。把当前下标 1 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 0, 0, 0, 0, 0, 0, 0]。
轮到下标 2(高 5,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈顶下标 1(高 7)不比 5 矮,停止弹栈。把当前下标 2 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 0, 0, 0, 0, 0, 0, 0]。
轮到下标 3(高 1,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈顶下标 2(高 5)不比 1 矮,停止弹栈。把当前下标 3 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 0, 0, 0, 0, 0, 0, 0]。
轮到下标 4(高 9,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈顶是下标 3(高 1,标红),它严格小于当前的 9,说明 9 就是它右边第一个更大值。填 ans[3] = 9,把下标 3 弹出。
栈顶是下标 2(高 5,标红),它严格小于当前的 9,说明 9 就是它右边第一个更大值。填 ans[2] = 9,把下标 2 弹出。
栈顶是下标 1(高 7,标红),它严格小于当前的 9,说明 9 就是它右边第一个更大值。填 ans[1] = 9,把下标 1 弹出。
栈已空,没有可结算的。把当前下标 4 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 0, 0, 0]。
轮到下标 5(高 2,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈顶下标 4(高 9)不比 2 矮,停止弹栈。把当前下标 5 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 0, 0, 0]。
轮到下标 6(高 5,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈顶是下标 5(高 2,标红),它严格小于当前的 5,说明 5 就是它右边第一个更大值。填 ans[5] = 5,把下标 5 弹出。
栈顶下标 4(高 9)不比 5 矮,停止弹栈。把当前下标 6 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 5, 0, 0]。
轮到下标 7(高 1,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
栈顶下标 6(高 5)不比 1 矮,停止弹栈。把当前下标 7 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 5, 0, 0]。
扫完整条数组。栈里还剩下标 4, 6, 7(蓝色),它们右边再没有更大的值,答案保持 0。最终 ans = [7, 9, 9, 9, 0, 5, 0, 0],和开头一致。
边界:空链返回空、单节点为 0、递减全 0、递增逐个结算。
面试常考:进出栈各一次所以 O(n);它就是「下一个更大元素」模板。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]: vals = [] while head: vals.append(head.val) head = head.next ans = [0] * len(vals) st = [] for i, v in enumerate(vals): while st and vals[st[-1]] < v: ans[st.pop()] = v st.append(i) return ans复杂度
- 时间：O(n)，遍历链表 O(n);扫描时每个下标最多进栈一次、出栈一次,均摊下来仍是 O(n)
- 空间：O(n)，数组 vals 占 O(n);单调栈最坏(严格递减时)装下全部 n 个下标
易错点
面试追问把动画讲成自己的话
追问单调栈为什么能把 O(n²) 降到 O(n)?
追问这题和「每日温度」(lc739)是一回事吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从链表中删去总和值为零的连续节点
LeetCode 1171 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题