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

2025-10-21 HGNULB 约 8 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

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

题意分析

给一条单链表，对每个节点求出它右边第一个严格大于它的节点值；不存在这样的节点时填 0。答案按节点顺序组成一个数组返回。

「严格大于」这四个字决定了后面弹栈条件用 < 还是 <=：相等的节点不算更大，不能把它弹出去。

用 0 表示「不存在」是安全的，因为题目保证节点值在 1 到 10^9 之间，0 不会与任何真实答案混淆；如果值域允许 0，就得换别的哨兵。

链表长度最大 10^4，值域到 10^9，所以只能存 int 而不能开值域数组，也说明平方级的两重循环（约 10^8 次比较）虽然勉强能过但不是出题意图。

结构上有个天然障碍：答案是按下标写回的数组，而单链表既不能随机访问也不能反向走。所以第一步几乎必然是把链表值抄进数组，把「链表问题」还原成「数组问题」。

边界要覆盖：只有一个节点（答案是 [0]）、严格递减的链表（答案全是 0）、以及存在相等值的链表（相等不算更大）。

解法：数组转换 + 单调栈

核心思路

暴力做法是对每个下标 i 向右扫，找到第一个比 values[i] 大的就停。逻辑最直白，但严格递减的输入下每个 i 都要扫到末尾，总共约 $n^2/2$ 次比较。

瓶颈在于「反复扫同一段后缀」。换个角度：一个下标从被读到、到它的答案被确定，中间这段时间它一直处于「待定」状态。而待定集合有个很好的性质——当一个新值 v 到来时，所有待定值中小于 v 的位置，答案在同一瞬间全部确定为 v；而待定值中不小于 v 的位置则原封不动继续等。

更进一步，这些待定值按下标从左到右看必然是不增的：因为下标 j 之所以还在待定，说明 j 之后到 i 之间没有出现过比 values[j] 更大的数，那么越靠右的待定值就越不可能超过它左边的待定值。这意味着「小于 v 的那批待定值」一定集中在最右侧连续的一段——正好对应栈顶。

于是用一个栈保存所有尚未确定答案的下标，维持的不变量是：处理下标 i 之前，栈里自底向上的下标递增、对应的值不增，且它们恰好构成 [0, i) 中所有还没拿到答案的位置。

转移动作只有两步：当 values[i] 严格大于栈顶下标对应的值时，反复弹栈并把 values[i] 写进被弹下标的答案位；弹不动之后把 i 自己压进去。弹栈条件必须是「栈顶值 < 当前值」而不是「<=」，因为题目要的是严格更大，相等的节点不能算答案。

扫描结束时仍留在栈里的下标，右边再没有更大的值，它们的答案就是初始值 0，所以不需要额外收尾。

解题步骤

先遍历链表把所有节点值抄进数组 values。理由是答案要按下标写回，而单链表不支持随机访问；抄一遍的代价是线性的，换来的是后面所有操作都能按下标寻址。

建长度为 n 的答案数组 res，全部初始化为 0。这一步同时把「不存在更大值」这个默认答案填好了，后面就不用再单独处理留在栈里的下标。

建一个存下标而不是存值的栈。存下标是关键：弹栈时既要知道该给谁写答案（下标），也要能拿到它的值去比较（用下标查数组），只存值就丢了写回位置。

从左到右遍历 i，先执行 while (栈非空 && values[栈顶] < values[i])，循环体里弹出栈顶并令 res[被弹下标] = values[i]。用 < 保证相等时不弹，对应题意里的「严格大于」。

内层循环结束后把 i 压栈。此时 values[i] 一定不大于新的栈顶值（否则循环还会继续），「自底向上值不增」的不变量得以维持。

遍历结束后直接返回 res，栈里剩下的下标不用管，它们的答案已经是 0。

以 head = [2,7,4,3,5] 走一遍：抄成 values = [2,7,4,3,5]，res = [0,0,0,0,0]，栈为空。i = 0 时栈空，直接压入，栈 = [0]。i = 1 时 values[1] = 7 大于栈顶 0 号位的 2，弹出 0 并写 res[0] = 7，栈空后压入 1，栈 = [1]，res = [7,0,0,0,0]。i = 2 时 values[2] = 4 不大于栈顶 1 号位的 7，不弹，直接压入，栈 = [1,2]。i = 3 时 values[3] = 3 不大于栈顶 2 号位的 4，压入，栈 = [1,2,3]。i = 4 时 values[4] = 5 大于栈顶 3 号位的 3，弹出并写 res[3] = 5；新栈顶是 2 号位的 4，仍小于 5，弹出并写 res[2] = 5；再看栈顶 1 号位的 7，不小于 5，停止弹栈，压入 4，栈 = [1,4]。遍历结束，res = [7,0,5,5,0]。栈里剩下的下标 1 和 4 对应的值 7 和 5，右侧确实没有更大的数，它们保持 0 正确。

代码实现

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)$，抄链表一趟；主循环里每个下标最多入栈一次、出栈一次，内层 while 的总执行次数不超过 n，均摊到每个位置是常数。

空间复杂度：$O(n)$，values 数组、res 数组和最坏装下全部下标的栈都是线性的；严格递减的输入会让栈真的涨到 n。

关键点总结

「右边第一个更大／更小的元素」这类问题的统一模板是：从左往右扫，栈里存待定下标，新值负责把栈里所有被它超过的位置一次性结清。识别出这个形状比记代码更重要。

栈里存下标而不是存值，因为出栈时既要写回答案位置又要比较大小；存值会丢掉位置信息，遇到要算距离或区间的变体（如 739、84）会直接卡住。

弹栈条件里的 < 和 <= 对应题面的「严格大于」和「大于等于」，有相等元素时两者结果不同，写之前先回题面确认一次。

把答案数组预填成「不存在」的默认值，扫描结束后就不必再处理栈中剩余元素，少一段收尾代码也少一个出错点。

面试视角：链表题看到「需要按下标写回答案」就应当主动说「先转成数组，代价 $O(n)$，换来随机访问」，这比硬在链表上折腾更能体现判断力；同时要能说清均摊分析——每个元素只进出栈各一次，所以内层 while 不会让复杂度变成平方级。

易错点总结

错误写法：弹栈条件写成 values[栈顶] <= values[i] → head = [2,2,3] 时第二个 2 会把第一个 2 当成答案，res[0] 被写成 2，而正确答案是 3，因为题目要的是严格更大。

错误写法：栈里存值而不是下标 → 弹栈时不知道该把答案写到 res 的哪一格，只能再开一个平行栈，白白多一份状态还容易不同步。

错误写法：内层用 if 而不是 while → head = [3,2,1,4] 时 4 只结清了 1 这一个位置，2 和 3 的答案仍是 0，正确答案是 [4,4,4,0]。

错误写法：res 不预填 0，或者预填成 -1 → 题目明确规定不存在时填 0，改成别的哨兵会让严格递减的输入整片答错。

错误写法：先把链表反转再从右往左处理，但忘了最后把答案数组也反转回去 → 答案顺序整体颠倒，样例 [2,1,5] 会返回 [0,5,5]。

错误写法：为省一次遍历而直接在链表上跑双层循环 → 逻辑能对，但 10^4 个节点的严格递减输入要做约 5 × 10^7 次指针跳转，链表的缓存局部性又差，实际耗时远比同规模数组差。

错误写法：Java 里用 Stack 类而不是 ArrayDeque → Stack 继承自 Vector，每个方法都带同步开销，且迭代顺序与栈序相反，一旦需要遍历栈内容就会出错。

错误写法：抄数组时直接拿形参 head 往后走，之后又想再用 head 跑第二趟 → 此时 head 已经是 null，第二趟一次都不执行；需要遍历两次就得先另存一份头指针。

相似题目

题目	难度	考察点
496. 下一个更大元素 I	简单	先在 nums2 上建映射，再按 nums1 查表
503. 下一个更大元素 II	中等	循环数组，需把下标扩成两倍长度取模
739. 每日温度	中等	答案要的是下标之差而非值，更依赖存下标
901. 股票价格跨度	中等	在线数据流上维护栈，还要合并已弹出的跨度
907. 子数组的最小值之和	中等	求每个元素作为最小值的左右边界并计数
456. 132 模式	中等	从右往左维护栈，同时追踪被弹出的次大值
LCR 038. 每日温度	中等	与 739 同题，可用来默写模板