LeetCode 1019. 链表中的下一个更大节点

约 5 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 需复习 2-5 字节 拼多多
标签
数组 栈 链表 单调栈

题目描述

✅ 1019. 链表中的下一个更大节点

image-20260928223914790

image-20260928223914791

题意分析

对链表中的每个节点，向后寻找第一个值严格大于它的节点，返回这个更大节点的值。找不到时该位置返回零，结果数组顺序与链表节点顺序一致。

“下一个更大”指位置最近的合格节点，不一定是紧邻的下一节点，也不是后面数值最小的更大值。相同值不能作为答案；需要返回值，而不是两个节点相隔的距离。

解法：数组转换 + 单调栈

核心思路

[!blue]

单链表不能按下标直接回查旧位置，所以先沿原顺序收集节点值到数组，方便把后来找到的答案写回对应位置。这个过程只移动遍历指针，不修改原链表连接。

从左到右扫描值数组，用栈保存尚未找到更大节点的下标。栈底到栈顶下标递增，对应值非递增。当前值大于栈顶对应值时，栈顶位置第一次等到了更大值，弹出该下标并把当前值写入它的答案。

因为扫描顺序就是从近到远，某个下标一直留在栈里，说明此前没有更大节点将它弹出；当前触发弹出的一定是它右侧第一个更大值。当前值还可能同时超过新的栈顶，所以要连续弹栈，直到栈顶不再比它小。

停止时，栈里更下面的值也不小于栈顶，当前值无法解决它们；再压入当前下标，非递增关系继续保持。相等值保留等待，遍历结束还在栈中的节点后面没有更大值，维持答案默认零。

解题步骤

  1. 遍历链表，将节点值按原顺序存入数组，准备全零答案数组与空下标栈。
  2. 从左到右读取当前值，只要它严格大于栈顶对应值，就弹出旧下标。
  3. 将当前值写入每个被弹出下标的答案，继续检查新的栈顶。
  4. 无法继续匹配时，压入当前下标，等待未来更大值。
  5. 扫描结束直接返回结果，未被弹出的位置保持零。

代码实现

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> values = new ArrayList<>();

        while (head != null) {
            values.add(head.val);
            head = head.next;
        }

        int n = values.size();
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            int val = values.get(i);

            // 当前值是这些待定位置首次遇到的严格更大值。
            while (!stack.isEmpty() && values.get(stack.peek()) < val) {
                res[stack.pop()] = val;
            }

            // 相等值保留等待，栈底到顶的值不增。
            stack.push(i);
        }

        return res;
    }
}

func nextLargerNodes(head *ListNode) []int {
    values := make([]int, 0)
    for head != nil {
        values = append(values, head.Val)
        head = head.Next
    }

    n := len(values)
    res := make([]int, n)
    stack := make([]int, 0)

    for i, val := range values {
        // 当前值是这些待定位置首次遇到的严格更大值。
        for len(stack) > 0 && values[stack[len(stack)-1]] < val {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = val
        }
        // 相等值保留等待，栈底到顶的值不增。
        stack = append(stack, i)
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，链表转数组为线性；之后每个下标压栈一次、至多弹出一次，总比较与更新次数仍为线性。
  • 空间复杂度：$O(n)$，保存节点值数组与待匹配下标栈；返回答案数组另占 $O(n)$。

关键点总结

[!green]

  • 栈保存还未定案的位置，当前更大值到来时集中为它们填写答案。
  • 从左到右扫描保证第一次触发匹配就是位置最近的更大节点。
  • 下标用于写回原位置，值用于比较和作为答案，两种作用需要区分。
  • 严格大于才匹配，相同值可以同时留在非递增栈中。

易错点总结

[!yellow]

  • 使用大于等于作为匹配条件，把相同值也当成更大节点。
  • 一次只弹一个下标，当前节点可能同时是多个旧位置的第一个更大值。
  • 将答案写到当前下标，当前节点其实还在等待自己的后续答案；应写入被弹出的旧下标。
  • 保存温差或下标距离，混淆其他单调栈题目，这里要写当前节点值。
  • 对值数组排序再查更大值，破坏链表中的先后位置，无法找到最近的后续节点。

相似题目

题目 难度 关联与区别
739. 每日温度 中等 同样用单调栈记录尚未找到更大值的位置，原题返回距离，本题返回后续节点值。
496. 下一个更大元素 I 简单 原题数组可直接索引，本题链表可先转成序列或在遍历时维护节点下标。
503. 下一个更大元素 II 中等 用单调栈确定最近的更大元素；本题先把链表值转为顺序序列处理，该题循环扫描以覆盖跨边界候选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/04162476
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！