题目描述

给定一个长度为 n 的链表，对于列表中的每个节点，查找下一个更大节点的值。返回一个整数数组 answer，其中 answer[i] 是第 i 个节点下一个更大节点的值。如果第 i 个节点没有下一个更大节点的值，设置 answer[i] = 0。

例如：链表 [2,1,5] → 输出 [5,5,0]

  • 节点 2：下一个更大的是 5
  • 节点 1：下一个更大的是 5
  • 节点 5：后面没有更大的，为 0

再如：链表 [2,7,4,3,5] → 输出 [7,0,5,5,0]

解题思路

本题是”下一个更大元素”问题的变种，只不过数据结构从数组变成了链表。核心思路依然是单调栈。

整体流程

  1. 链表转数组：首先遍历链表，将所有节点的值存入一个 ArrayList 中，这样可以方便地通过下标随机访问。同时记录元素总数 n。

  2. 单调递减栈求解：使用一个单调递减栈（存储下标），从左到右遍历数组：

    • 当栈不为空，且当前元素 nums.get(i) 大于栈顶下标对应元素时：
      • 弹出栈顶下标 index，意味着节点 index 找到了下一个更大的值。
      • 设置 answer[index] = nums.get(i)。
    • 将当前下标 i 入栈。

  3. 遍历结束后，栈中剩余的下标对应的元素没有找到下一个更大的值，answer 数组中对应位置保持默认值 0。

为什么用单调栈？

对于类似”找下一个更大/更小的元素”的问题，单调栈可以将暴力的 O(n²) 降低到 O(n)。核心思想是：

  • 当遇到一个更大的元素时，栈中所有比它小的元素都在”等待”被匹配，一旦遇到更大的，就逐个结算。
  • 栈的单调性保证了从未被弹出的元素不会被遗漏。

与 LeetCode 739 “每日温度” 的对比

本题与第 739 题几乎完全一致，唯一区别是数据来源是链表而非数组，以及”下一个更大”判定的对象是数值本身而非下标差值。解法思路完全相同：链表转数组 + 单调栈。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表长度。链表遍历一次，单调栈处理每个元素入栈出栈各一次，均为 O(n)。
  • 空间复杂度：O(n)，需要存储数组形式的链表节点值以及单调栈，均为 O(n) 级别。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package code.J1019;

import datastructure.ListNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class J1019 {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            nums.add(curr.val);
            curr = curr.next;
        }
        int n = nums.size();
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums.get(i) > nums.get(stack.peek())) {
                int index = stack.pop();
                answer[index] = nums.get(i);
            }
            stack.push(i);
        }
        return answer;
    }
}