 暴力到线性解法)
单调栈解 LeetCode 1019 链表中的下一个更大节点从 O(N²) 暴力到线性解法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇以 LeetCode 1019「链表中的下一个更大节点」为主线完整讲解如何利用单调栈把「为每个节点求其后第一个更大值」的问题从 O(N²) 暴力优化到 O(N) 线性时间。读完本文你将理解单调栈的维护原理与通用代码模板掌握 1019 的完整解法与逐步推演并能把它与仓库中同族的 739「每日温度」题解daily/2019-06-06.md进行对比归纳形成应对「下一个更大/更小元素」类题目的可复用模板。题目描述与输入输出格式题解原文档位于 problems/1019.next-greater-node-in-linked-list.md该题在仓库的难度分级中被归入 Medium 难度收录于 collections/medium.md。给出一个以头节点head作为第一个节点的链表链表中的节点分别编号为node_1, node_2, node_3, ...。每个节点都可能有下一个更大值next larger value对于node_i如果其next_larger(node_i)是node_j.val那么就有j i且node_j.val node_i.val而j是可能的选项中最小的那个。如果不存在这样的j那么下一个更大值为 0。要求返回整数答案数组answer其中answer[i] next_larger(node_{i1})。注意题目示例中诸如[2,1,5]这样的输入不是输出是链表的序列化表示其头节点的值为 2第二个节点值为 1第三个节点值为 5。三个官方示例如下输入链表序列化表示输出[2,1,5][5,5,0][2,7,4,3,5][7,0,5,5,0][1,7,5,1,9,2,5,1][7,9,9,9,0,5,0,0]题目约束对于链表中的每个节点1 node.val 10^9给定列表的长度在[0, 10000]范围内。前置知识链表、栈。题解文档还标注了该题曾出现在腾讯、字节的面试中。思路为什么是单调栈看完题目就应该想到单调栈。LeetCode 上关于单调栈的题目还不少难度都不小但是一旦你掌握了这个算法那么这些题目对你来说都不是问题了。如果不用单调栈可以暴力 O(N²) 解决双层循环外层枚举每个节点内层向后扫描寻找第一个更大的值。这种做法对于长度上限 10000 的链表来说开销明显偏大题解原文认为「这种做法应该是过不了关的」。使用单调栈则可以将时间复杂度降低到线性代价是额外 O(N) 的空间复杂度。顾名思义单调栈即满足单调性的栈结构。与单调队列相比其只在一端进行进出。为了描述方便下面以维护一个整数的单调递减栈为例这是 1019 所需的形态。将一个元素插入单调栈时为了维护栈的单调性需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。例如栈中自顶向下的元素为 1, 2, 4, 5插入元素 3 时为了保证单调性需要依次弹出元素最开始栈是这样的[5,4,2,1]为了维护递减特性1, 2 需要被移除此时栈是[5,4]我们将 3 push 到栈顶即可此时栈是这样的[5,4,3]。用代码描述如下def monoStack(list): st [] for v in list: while len(st) 0 and v st[-1]: st.pop() st.append(v) return st monoStack([5, 4, 2, 1, 3]) # output: [5, 4, 3]单调栈的核心性质可以这样理解当一个元素被后来的更大元素「弹出」时这个弹出点就是它之后第一个比它大的位置——这正是「下一个更大值」问题的答案来源。仓库中 thinkings/monotone-stack.md 对单调栈有更系统的论述其适用场景就是求解「下一个大于 xxx」或「下一个小于 xxx」类题目并给出了哨兵法技巧在序列右侧添加一个极小值简化收尾逻辑与通用伪代码模板。1019 完整解法与逐步推演题解原文给出的 Python 实现如下栈中存储「结果下标 节点值」的元组res数组先用 0 占位后续被命中时再回填答案# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def nextLargerNodes(self, head): res, st [], [] while head: while len(st) 0 and head.val st[-1][1]: res[st.pop()[0]] head.val st.append((len(res), head.val)) res.append(0) head head.next return res代码逻辑拆解顺次遍历链表每个节点先参与「弹栈比对」只要栈顶节点的值小于当前节点值就弹出栈顶并把当前节点的值写入其对应的res位置st.pop()[0]是之前记录的结果下标比对结束后把当前节点的(结果下标, 节点值)压栈同时在res末尾追加占位 0走到链表末尾仍留在栈中的节点说明其后不存在更大值res中保留的占位 0 恰好就是它们的答案无需额外收尾。以示例 2[2,7,4,3,5]做一次逐步推演步骤当前节点值弹栈动作栈自顶向下存 (下标, 值)res12无[(0,2)][0]27弹出 (0,2)res[0]7[(1,7)][7,0]34无[(2,4),(1,7)][7,0,0]43无[(3,3),(2,4),(1,7)][7,0,0,0]55弹出 (3,3) res[3]5弹出 (2,4) res[2]5[(4,5),(1,7)][7,0,5,5,0]最终返回[7,0,5,5,0]与期望输出一致。注意第 2、4 步的「连续弹栈」5 一次性地解决了 3 和 4 两个待定点这正是单调摊还分析中「每个元素至多弹栈一次」的直观体现。复杂度分析设 N 为链表长度时间复杂度O(N)。每个节点最多入栈一次、出栈一次内外层循环的总弹出次数不超过 N 次空间复杂度O(N)。最坏情况下例如链表递减栈中可能同时存放全部 N 个节点。与 739「每日温度」的对照同族问题的模板差异仓库中的相关题解 daily/2019-06-06.md 收录了 739「每日温度」它和 1019 是同一套单调栈模板的两种落地栈存「下标」、答案存「下标差」。其单调递减栈解法JavaScript为/** * param {number[]} T * return {number[]} * 递减栈 */ var dailyTemperatures function(T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while(stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };两题的结构化对照维度1019 链表中的下一个更大节点739 每日温度数据结构载体链表顺次遍历数组按下标遍历栈中存储(结果下标, 节点值)元组元素下标 i命中条件当前值 栈顶值当前温度 栈顶下标对应温度答案含义下一个更大的值head.val等待的天数i - peek无解兜底res占位 0result占位 0复杂度时间 O(N)、空间 O(N)时间 O(N)、空间 O(N)可以看出 1019 的解法就是把「按值回填」和「按差值回填」做了切换739 的答案是距离下标之差1019 的答案是值本身因此 1019 的栈里必须同时携带下标回填用和值比较用。掌握这一对照后thinkings/monotone-stack.md 中给出的伪代码模板栈存下标、ans 初始化为默认值、while 循环弹出并回填可以直接迁移到任何「下一个更大/更小元素」题目上只需要修改回填公式和比较方向。空间优化的可能性与相关题目题解原文的「扩展」部分指出该题甚至可以做到 O(1) 的空间复杂度参考其引用的 LeetCode 社区 C# 解法O(n) time O(1) space。这类做法的一般思路是复用链表节点自身的存储例如改写node.val来承载中间结果从而省掉额外的 O(N) 结果数组其代价是破坏原始链表数据仅在不要求保留原链表的场景下适用。单调栈在仓库中的知识网络还包括以下题解可作为本篇的延伸阅读路径42. 接雨水——单调栈逐层计算水量84. 柱状图中最大的矩形——「下一个更小元素」方向的单调栈应用739. 每日温度——本文直接对照题其余推荐题见 thinkings/monotone-stack.md 的「题目推荐」316. 去除重复字母、402. 移掉 K 位数字、496. 下一个更大元素 I、581. 最短无序连续子数组、901. 股票价格跨度。总结1019 的关键点只有两个——单调栈单调递减栈与单调栈的代码模板。按「先弹栈回填、再压栈占位」的固定顺序实现即可在 O(N) 时间内完成链表上「下一个更大值」的批量求解。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/18 14:45:56 · 阅读 1.2k 单调栈解 LeetCode 1019 链表中的下一个更大节点：从 O(N²) 暴力到线性解法
单调栈解 LeetCode 1019 链表中的下一个更大节点从 O(N²) 暴力到线性解法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇以 LeetCode 1019「链表中的下一个更大节点」为主线完整讲解如何利用单调栈把「为每个节点求其后第一个更大值」的问题从 O(N²) 暴力优化到 O(N) 线性时间。读完本文你将理解单调栈的维护原理与通用代码模板掌握 1019 的完整解法与逐步推演并能把它与仓库中同族的 739「每日温度」题解daily/2019-06-06.md进行对比归纳形成应对「下一个更大/更小元素」类题目的可复用模板。题目描述与输入输出格式题解原文档位于 problems/1019.next-greater-node-in-linked-list.md该题在仓库的难度分级中被归入 Medium 难度收录于 collections/medium.md。给出一个以头节点head作为第一个节点的链表链表中的节点分别编号为node_1, node_2, node_3, ...。每个节点都可能有下一个更大值next larger value对于node_i如果其next_larger(node_i)是node_j.val那么就有j i且node_j.val node_i.val而j是可能的选项中最小的那个。如果不存在这样的j那么下一个更大值为 0。要求返回整数答案数组answer其中answer[i] next_larger(node_{i1})。注意题目示例中诸如[2,1,5]这样的输入不是输出是链表的序列化表示其头节点的值为 2第二个节点值为 1第三个节点值为 5。三个官方示例如下输入链表序列化表示输出[2,1,5][5,5,0][2,7,4,3,5][7,0,5,5,0][1,7,5,1,9,2,5,1][7,9,9,9,0,5,0,0]题目约束对于链表中的每个节点1 node.val 10^9给定列表的长度在[0, 10000]范围内。前置知识链表、栈。题解文档还标注了该题曾出现在腾讯、字节的面试中。思路为什么是单调栈看完题目就应该想到单调栈。LeetCode 上关于单调栈的题目还不少难度都不小但是一旦你掌握了这个算法那么这些题目对你来说都不是问题了。如果不用单调栈可以暴力 O(N²) 解决双层循环外层枚举每个节点内层向后扫描寻找第一个更大的值。这种做法对于长度上限 10000 的链表来说开销明显偏大题解原文认为「这种做法应该是过不了关的」。使用单调栈则可以将时间复杂度降低到线性代价是额外 O(N) 的空间复杂度。顾名思义单调栈即满足单调性的栈结构。与单调队列相比其只在一端进行进出。为了描述方便下面以维护一个整数的单调递减栈为例这是 1019 所需的形态。将一个元素插入单调栈时为了维护栈的单调性需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。例如栈中自顶向下的元素为 1, 2, 4, 5插入元素 3 时为了保证单调性需要依次弹出元素最开始栈是这样的[5,4,2,1]为了维护递减特性1, 2 需要被移除此时栈是[5,4]我们将 3 push 到栈顶即可此时栈是这样的[5,4,3]。用代码描述如下def monoStack(list): st [] for v in list: while len(st) 0 and v st[-1]: st.pop() st.append(v) return st monoStack([5, 4, 2, 1, 3]) # output: [5, 4, 3]单调栈的核心性质可以这样理解当一个元素被后来的更大元素「弹出」时这个弹出点就是它之后第一个比它大的位置——这正是「下一个更大值」问题的答案来源。仓库中 thinkings/monotone-stack.md 对单调栈有更系统的论述其适用场景就是求解「下一个大于 xxx」或「下一个小于 xxx」类题目并给出了哨兵法技巧在序列右侧添加一个极小值简化收尾逻辑与通用伪代码模板。1019 完整解法与逐步推演题解原文给出的 Python 实现如下栈中存储「结果下标 节点值」的元组res数组先用 0 占位后续被命中时再回填答案# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def nextLargerNodes(self, head): res, st [], [] while head: while len(st) 0 and head.val st[-1][1]: res[st.pop()[0]] head.val st.append((len(res), head.val)) res.append(0) head head.next return res代码逻辑拆解顺次遍历链表每个节点先参与「弹栈比对」只要栈顶节点的值小于当前节点值就弹出栈顶并把当前节点的值写入其对应的res位置st.pop()[0]是之前记录的结果下标比对结束后把当前节点的(结果下标, 节点值)压栈同时在res末尾追加占位 0走到链表末尾仍留在栈中的节点说明其后不存在更大值res中保留的占位 0 恰好就是它们的答案无需额外收尾。以示例 2[2,7,4,3,5]做一次逐步推演步骤当前节点值弹栈动作栈自顶向下存 (下标, 值)res12无[(0,2)][0]27弹出 (0,2)res[0]7[(1,7)][7,0]34无[(2,4),(1,7)][7,0,0]43无[(3,3),(2,4),(1,7)][7,0,0,0]55弹出 (3,3) res[3]5弹出 (2,4) res[2]5[(4,5),(1,7)][7,0,5,5,0]最终返回[7,0,5,5,0]与期望输出一致。注意第 2、4 步的「连续弹栈」5 一次性地解决了 3 和 4 两个待定点这正是单调摊还分析中「每个元素至多弹栈一次」的直观体现。复杂度分析设 N 为链表长度时间复杂度O(N)。每个节点最多入栈一次、出栈一次内外层循环的总弹出次数不超过 N 次空间复杂度O(N)。最坏情况下例如链表递减栈中可能同时存放全部 N 个节点。与 739「每日温度」的对照同族问题的模板差异仓库中的相关题解 daily/2019-06-06.md 收录了 739「每日温度」它和 1019 是同一套单调栈模板的两种落地栈存「下标」、答案存「下标差」。其单调递减栈解法JavaScript为/** * param {number[]} T * return {number[]} * 递减栈 */ var dailyTemperatures function(T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while(stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };两题的结构化对照维度1019 链表中的下一个更大节点739 每日温度数据结构载体链表顺次遍历数组按下标遍历栈中存储(结果下标, 节点值)元组元素下标 i命中条件当前值 栈顶值当前温度 栈顶下标对应温度答案含义下一个更大的值head.val等待的天数i - peek无解兜底res占位 0result占位 0复杂度时间 O(N)、空间 O(N)时间 O(N)、空间 O(N)可以看出 1019 的解法就是把「按值回填」和「按差值回填」做了切换739 的答案是距离下标之差1019 的答案是值本身因此 1019 的栈里必须同时携带下标回填用和值比较用。掌握这一对照后thinkings/monotone-stack.md 中给出的伪代码模板栈存下标、ans 初始化为默认值、while 循环弹出并回填可以直接迁移到任何「下一个更大/更小元素」题目上只需要修改回填公式和比较方向。空间优化的可能性与相关题目题解原文的「扩展」部分指出该题甚至可以做到 O(1) 的空间复杂度参考其引用的 LeetCode 社区 C# 解法O(n) time O(1) space。这类做法的一般思路是复用链表节点自身的存储例如改写node.val来承载中间结果从而省掉额外的 O(N) 结果数组其代价是破坏原始链表数据仅在不要求保留原链表的场景下适用。单调栈在仓库中的知识网络还包括以下题解可作为本篇的延伸阅读路径42. 接雨水——单调栈逐层计算水量84. 柱状图中最大的矩形——「下一个更小元素」方向的单调栈应用739. 每日温度——本文直接对照题其余推荐题见 thinkings/monotone-stack.md 的「题目推荐」316. 去除重复字母、402. 移掉 K 位数字、496. 下一个更大元素 I、581. 最短无序连续子数组、901. 股票价格跨度。总结1019 的关键点只有两个——单调栈单调递减栈与单调栈的代码模板。按「先弹栈回填、再压栈占位」的固定顺序实现即可在 O(N) 时间内完成链表上「下一个更大值」的批量求解。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考