LeetCode-Go 题解精讲1019. Next Greater Node In Linked List 链表中下一个更大节点的单调栈解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 leetcode/1019.Next-Greater-Node-In-Linked-List 的题目文档与 Go 实现系统讲解「链表中下一个更大节点」问题的完整解法。你将掌握如何把链表问题转化为数组/索引问题、如何用单调栈在 O(n) 时间内求出每个节点右侧第一个比它大的值并通过仓库内的单元测试验证算法正确性。这套思路与 739、496、503 题一脉相承是解决下一个更大元素系列问题的通用范式。题目描述给定一个以 head 为头节点的单链表将链表中的节点编号为 node₁, node₂, node₃, …。对于每个节点 node_i定义其「下一个更大值」next_larger(node_i) 为满足 j i、node_j.val node_i.val 且 j 尽可能小的那个 node_j.val。如果不存在这样的 j则下一个更大值为 0。要求返回整数数组 answer其中 answer[i] next_larger(node_{i1})。注意示例输入中的数组[2,1,5]表示链表的序列化形式——头节点值为 2第二个节点值为 1第三个节点值为 5。示例示例 1Input: [2,1,5] Output: [5,5,0]示例 2Input: [2,7,4,3,5] Output: [7,0,5,5,0]示例 3Input: [1,7,5,1,9,2,5,1] Output: [7,9,9,9,0,5,0,0]约束条件链表中每个节点的取值范围1 node.val 10^9链表长度范围[0, 10000]即链表可以为空题目大意给出一个链表要求找出每个结点后面比该结点值大的第一个结点如果找不到这样的结点则该位置输出 0。需要特别注意的是下一个更大与最大不同对于结点 5它右侧的 9 和 8 都比它大但答案是 9第一个出现的更大值而不是 8。解题思路总览原文档明确指出这一题与第 739 题每日温度、第 496 题下一个更大元素 I、第 503 题下一个更大元素 II类似共有两种解题方法普通做法先把链表中的数字全部存入数组再用两层循环暴力求解。整道题的思路就与第 739 题的普通解法完全一致。优化做法用单调栈维护一个单调递减的栈一次遍历即可求出全部答案。下面结合仓库源码逐一展开。方法一单调栈推荐O(n)仓库中的标准解法位于 1019. Next Greater Node In Linked List.go实现如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode // 解法一 单调栈 func nextLargerNodes(head *ListNode) []int { type node struct { index, val int } var monoStack []node var res []int for head ! nil { for len(monoStack) 0 monoStack[len(monoStack)-1].val head.Val { res[monoStack[len(monoStack)-1].index] head.Val monoStack monoStack[:len(monoStack)-1] } monoStack append(monoStack, node{len(res), head.Val}) res append(res, 0) head head.Next } return res }核心设计要点复用链表结点定义代码通过type ListNode structures.ListNode直接复用仓库 structures/ListNode.go 中定义的链表结点type ListNode struct { Val int Next *ListNode }栈内元素携带下标由于链表本身没有随机访问能力而最终结果res是按链表下标从 0 开始组织的数组所以栈中每个元素记录(index, val)二元组——index 是结点在链表中的位置val 是结点值。这样出栈时才能精确回填res[index]。单调递减栈的维护逻辑遍历链表时只要栈顶结点的值小于当前结点值head.Val说明当前结点就是栈顶结点右侧第一个更大的值于是执行回填res[栈顶.index] head.Val并弹出栈顶随后把当前结点(len(res), head.Val)压入栈并为它预先在res中追加一个占位0若最终没被回填说明右侧没有更大值保持 0 即可。默认值技巧res每次追加 0 作为默认值只有被后续更大结点命中时才改写天然满足题目找不到则输出 0的要求省去了单独初始化数组的步骤。单调栈运行过程演示以示例 2 的链表[2,7,4,3,5]为例步骤当前结点栈操作res12入栈 (0,2)[0,0,0,0,0]272 7回填 res[0]7弹出 (0,2)入栈 (1,7)[7,0,0,0,0]347 ≥ 4直接入栈 (2,4)[7,0,0,0,0]434 ≥ 3直接入栈 (3,3)[7,0,0,0,0]553 5回填 res[3]5弹出 (3,3)4 5回填 res[2]5弹出 (2,4)入栈 (4,5)[7,0,5,5,0]最终返回[7,0,5,5,0]与题目输出一致。可见栈始终维持从栈底到栈顶单调递减的性质栈内只保留尚未找到下一个更大值的结点。复杂度分析时间复杂度O(n)。每个结点最多入栈一次、出栈一次整体线性。空间复杂度O(n)。栈与结果数组均与链表长度成正比。方法二普通双重循环O(n²)如果不使用单调栈可以先把链表值全部拷贝到数组中再对每个位置向右扫描寻找第一个更大的值。这与仓库中 739. Daily Temperatures.go 的普通解法dailyTemperatures思路一致// 解法一 普通做法 func dailyTemperatures(T []int) []int { res, j : make([]int, len(T)), 0 for i : 0; i len(T); i { for j i 1; j len(T); j { if T[j] T[i] { res[i] j - i break } } } return res }套用到本题只需将j - i距离改为T[j]值即可func nextLargerNodesBruteForce(head *ListNode) []int { vals : structures.List2Ints(head) res : make([]int, len(vals)) for i : 0; i len(vals); i { for j : i 1; j len(vals); j { if vals[j] vals[i] { res[i] vals[j] break } } } return res }其中 List2Ints 是仓库提供的链表转数组工具函数。该解法的时间复杂度为 O(n²)空间复杂度 O(n)。虽然正确但在链表长度达到 10000 的上限时会退化到约 10⁸ 次比较因此单调栈才是本题的推荐解法。与 739 / 496 / 503 题的关联与差异原文档特意指出本题与第 739、496、503 题属于同一家族仓库中这几题的实现可以对照学习题目数据形态目标差异点739. Daily Temperatures数组右侧第一个更大值的距离栈内存下标回填i - idx496. Next Greater Element I两个数组子集元素在父数组中的下一个更大值配合哈希表记录位置未找到输出 -1503. Next Greater Element II循环数组下一个更大值可绕圈遍历2*n次并用取模模拟环未找到输出 -11019. Next Greater Node In Linked List链表下一个更大值需先记录结点下标未找到输出0对比 503. Next Greater Element II.go 的单调栈实现可以发现503 题栈内存的是数组下标通过nums[i%len(nums)]处理环形1019 题因为链表无法按下标访问所以栈内存(index, val)二元组。二者的弹栈回填逻辑栈顶.val 当前值时回填并弹出完全同构掌握其中一题即可举一反三。单元测试与验证仓库为本题提供了完整的测试用例位于 1019. Next Greater Node In Linked List_test.go。测试通过structures.Ints2List把数组序列化成链表该函数定义在 structures/ListNode.go空数组返回 nil 链表再对nextLargerNodes进行断言qs : []question1019{ { para1019{[]int{2, 1, 5}}, ans1019{[]int{5, 5, 0}}, }, { para1019{[]int{2, 7, 4, 3, 5}}, ans1019{[]int{7, 0, 5, 5, 0}}, }, { para1019{[]int{1, 7, 5, 1, 9, 2, 5, 1}}, ans1019{[]int{7, 9, 9, 9, 0, 5, 0, 0}}, }, { para1019{[]int{1, 7, 5, 1, 9, 2, 5, 6, 7, 8, 1}}, ans1019{[]int{7, 9, 9, 9, 0, 5, 6, 7, 8, 0, 0}}, }, }除题目自带的三个示例外测试还补充了一个更长的用例[1,7,5,1,9,2,5,6,7,8,1]用于覆盖连续多次弹栈回填与尾部单调递减无更大值的场景。测试入口Test_Problem1019会逐条打印输入输出便于肉眼核对。边界情况与注意事项空链表链表长度可为 0。此时for head ! nil循环不进入返回空的res符合预期。值相等不触发回填弹栈条件为严格小于栈顶.val head.Val。若右侧存在相等的值它不算更大不应回填——这是题目定义node_j.val node_i.val的直接体现。单调递减的尾巴若链表尾部是严格递减序列如[5,4,3]栈中元素永远不会被弹出res保持默认 0正确表示找不到下一个更大值。数值范围结点值最大可达 10⁹用 Go 的int类型即可安全存储无溢出风险。环状链表防护虽然本题输入保证是普通链表但仓库的List2Ints工具对环状链表设置了 100 层的深度上限检查并 panic可参考 structures/ListNode.go 了解其防护设计。总结1019 题的核心套路是链表转索引思维 单调递减栈栈中保存尚未找到答案的结点连同其下标遇到更大的值就连续弹栈回填最终未被回填的位置输出 0。仓库中的 Go 实现用(index, val)二元组优雅地弥补了链表无法随机访问的短板代码简洁且时间复杂度仅为 O(n)。配合 739、496、503 三题的对照阅读可以系统掌握下一个更大元素这一经典单调栈应用场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解精讲：1019. Next Greater Node In Linked List 链表中下一个更大节点的单调栈解法
LeetCode-Go 题解精讲1019. Next Greater Node In Linked List 链表中下一个更大节点的单调栈解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 leetcode/1019.Next-Greater-Node-In-Linked-List 的题目文档与 Go 实现系统讲解「链表中下一个更大节点」问题的完整解法。你将掌握如何把链表问题转化为数组/索引问题、如何用单调栈在 O(n) 时间内求出每个节点右侧第一个比它大的值并通过仓库内的单元测试验证算法正确性。这套思路与 739、496、503 题一脉相承是解决下一个更大元素系列问题的通用范式。题目描述给定一个以 head 为头节点的单链表将链表中的节点编号为 node₁, node₂, node₃, …。对于每个节点 node_i定义其「下一个更大值」next_larger(node_i) 为满足 j i、node_j.val node_i.val 且 j 尽可能小的那个 node_j.val。如果不存在这样的 j则下一个更大值为 0。要求返回整数数组 answer其中 answer[i] next_larger(node_{i1})。注意示例输入中的数组[2,1,5]表示链表的序列化形式——头节点值为 2第二个节点值为 1第三个节点值为 5。示例示例 1Input: [2,1,5] Output: [5,5,0]示例 2Input: [2,7,4,3,5] Output: [7,0,5,5,0]示例 3Input: [1,7,5,1,9,2,5,1] Output: [7,9,9,9,0,5,0,0]约束条件链表中每个节点的取值范围1 node.val 10^9链表长度范围[0, 10000]即链表可以为空题目大意给出一个链表要求找出每个结点后面比该结点值大的第一个结点如果找不到这样的结点则该位置输出 0。需要特别注意的是下一个更大与最大不同对于结点 5它右侧的 9 和 8 都比它大但答案是 9第一个出现的更大值而不是 8。解题思路总览原文档明确指出这一题与第 739 题每日温度、第 496 题下一个更大元素 I、第 503 题下一个更大元素 II类似共有两种解题方法普通做法先把链表中的数字全部存入数组再用两层循环暴力求解。整道题的思路就与第 739 题的普通解法完全一致。优化做法用单调栈维护一个单调递减的栈一次遍历即可求出全部答案。下面结合仓库源码逐一展开。方法一单调栈推荐O(n)仓库中的标准解法位于 1019. Next Greater Node In Linked List.go实现如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode // 解法一 单调栈 func nextLargerNodes(head *ListNode) []int { type node struct { index, val int } var monoStack []node var res []int for head ! nil { for len(monoStack) 0 monoStack[len(monoStack)-1].val head.Val { res[monoStack[len(monoStack)-1].index] head.Val monoStack monoStack[:len(monoStack)-1] } monoStack append(monoStack, node{len(res), head.Val}) res append(res, 0) head head.Next } return res }核心设计要点复用链表结点定义代码通过type ListNode structures.ListNode直接复用仓库 structures/ListNode.go 中定义的链表结点type ListNode struct { Val int Next *ListNode }栈内元素携带下标由于链表本身没有随机访问能力而最终结果res是按链表下标从 0 开始组织的数组所以栈中每个元素记录(index, val)二元组——index 是结点在链表中的位置val 是结点值。这样出栈时才能精确回填res[index]。单调递减栈的维护逻辑遍历链表时只要栈顶结点的值小于当前结点值head.Val说明当前结点就是栈顶结点右侧第一个更大的值于是执行回填res[栈顶.index] head.Val并弹出栈顶随后把当前结点(len(res), head.Val)压入栈并为它预先在res中追加一个占位0若最终没被回填说明右侧没有更大值保持 0 即可。默认值技巧res每次追加 0 作为默认值只有被后续更大结点命中时才改写天然满足题目找不到则输出 0的要求省去了单独初始化数组的步骤。单调栈运行过程演示以示例 2 的链表[2,7,4,3,5]为例步骤当前结点栈操作res12入栈 (0,2)[0,0,0,0,0]272 7回填 res[0]7弹出 (0,2)入栈 (1,7)[7,0,0,0,0]347 ≥ 4直接入栈 (2,4)[7,0,0,0,0]434 ≥ 3直接入栈 (3,3)[7,0,0,0,0]553 5回填 res[3]5弹出 (3,3)4 5回填 res[2]5弹出 (2,4)入栈 (4,5)[7,0,5,5,0]最终返回[7,0,5,5,0]与题目输出一致。可见栈始终维持从栈底到栈顶单调递减的性质栈内只保留尚未找到下一个更大值的结点。复杂度分析时间复杂度O(n)。每个结点最多入栈一次、出栈一次整体线性。空间复杂度O(n)。栈与结果数组均与链表长度成正比。方法二普通双重循环O(n²)如果不使用单调栈可以先把链表值全部拷贝到数组中再对每个位置向右扫描寻找第一个更大的值。这与仓库中 739. Daily Temperatures.go 的普通解法dailyTemperatures思路一致// 解法一 普通做法 func dailyTemperatures(T []int) []int { res, j : make([]int, len(T)), 0 for i : 0; i len(T); i { for j i 1; j len(T); j { if T[j] T[i] { res[i] j - i break } } } return res }套用到本题只需将j - i距离改为T[j]值即可func nextLargerNodesBruteForce(head *ListNode) []int { vals : structures.List2Ints(head) res : make([]int, len(vals)) for i : 0; i len(vals); i { for j : i 1; j len(vals); j { if vals[j] vals[i] { res[i] vals[j] break } } } return res }其中 List2Ints 是仓库提供的链表转数组工具函数。该解法的时间复杂度为 O(n²)空间复杂度 O(n)。虽然正确但在链表长度达到 10000 的上限时会退化到约 10⁸ 次比较因此单调栈才是本题的推荐解法。与 739 / 496 / 503 题的关联与差异原文档特意指出本题与第 739、496、503 题属于同一家族仓库中这几题的实现可以对照学习题目数据形态目标差异点739. Daily Temperatures数组右侧第一个更大值的距离栈内存下标回填i - idx496. Next Greater Element I两个数组子集元素在父数组中的下一个更大值配合哈希表记录位置未找到输出 -1503. Next Greater Element II循环数组下一个更大值可绕圈遍历2*n次并用取模模拟环未找到输出 -11019. Next Greater Node In Linked List链表下一个更大值需先记录结点下标未找到输出0对比 503. Next Greater Element II.go 的单调栈实现可以发现503 题栈内存的是数组下标通过nums[i%len(nums)]处理环形1019 题因为链表无法按下标访问所以栈内存(index, val)二元组。二者的弹栈回填逻辑栈顶.val 当前值时回填并弹出完全同构掌握其中一题即可举一反三。单元测试与验证仓库为本题提供了完整的测试用例位于 1019. Next Greater Node In Linked List_test.go。测试通过structures.Ints2List把数组序列化成链表该函数定义在 structures/ListNode.go空数组返回 nil 链表再对nextLargerNodes进行断言qs : []question1019{ { para1019{[]int{2, 1, 5}}, ans1019{[]int{5, 5, 0}}, }, { para1019{[]int{2, 7, 4, 3, 5}}, ans1019{[]int{7, 0, 5, 5, 0}}, }, { para1019{[]int{1, 7, 5, 1, 9, 2, 5, 1}}, ans1019{[]int{7, 9, 9, 9, 0, 5, 0, 0}}, }, { para1019{[]int{1, 7, 5, 1, 9, 2, 5, 6, 7, 8, 1}}, ans1019{[]int{7, 9, 9, 9, 0, 5, 6, 7, 8, 0, 0}}, }, }除题目自带的三个示例外测试还补充了一个更长的用例[1,7,5,1,9,2,5,6,7,8,1]用于覆盖连续多次弹栈回填与尾部单调递减无更大值的场景。测试入口Test_Problem1019会逐条打印输入输出便于肉眼核对。边界情况与注意事项空链表链表长度可为 0。此时for head ! nil循环不进入返回空的res符合预期。值相等不触发回填弹栈条件为严格小于栈顶.val head.Val。若右侧存在相等的值它不算更大不应回填——这是题目定义node_j.val node_i.val的直接体现。单调递减的尾巴若链表尾部是严格递减序列如[5,4,3]栈中元素永远不会被弹出res保持默认 0正确表示找不到下一个更大值。数值范围结点值最大可达 10⁹用 Go 的int类型即可安全存储无溢出风险。环状链表防护虽然本题输入保证是普通链表但仓库的List2Ints工具对环状链表设置了 100 层的深度上限检查并 panic可参考 structures/ListNode.go 了解其防护设计。总结1019 题的核心套路是链表转索引思维 单调递减栈栈中保存尚未找到答案的结点连同其下标遇到更大的值就连续弹栈回填最终未被回填的位置输出 0。仓库中的 Go 实现用(index, val)二元组优雅地弥补了链表无法随机访问的短板代码简洁且时间复杂度仅为 O(n)。配合 739、496、503 三题的对照阅读可以系统掌握下一个更大元素这一经典单调栈应用场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考