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

Categories:

题目描述
思路分析
1. 解法一：单调栈（推荐）
相似题目

题目描述

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

思路分析

解法一：单调栈（推荐）

核心思路：

先遍历链表转为数组，便于下标访问。

维护单调递减栈，栈内存储下标。

当遇到更大值时，弹出栈顶并记录答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(n)，用于数组与栈。

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

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
}

相似题目

题目	难度	考察点
496. 下一个更大元素 I	简单	单调栈
503. 下一个更大元素 II	中等	单调栈
739. 每日温度	中等	单调栈
1475. 商品折扣后的最终价格	简单	单调栈
901. 股票价格跨度	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/04162476