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

• Categories:

• Tags:

1. 题目描述
2. 思路分析
3. 参考代码
4. 相似题目

题目描述

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

思路分析

单调递减栈

参考代码

func nextLargerNodes(head *ListNode) []int {
	var nums []int
	cur := head
	for cur != nil {
		nums = append(nums, cur.Val)
		cur = cur.Next
	}

	res := make([]int, len(nums))
	var stack []int

	for i, num := range nums {
		for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
			res[stack[len(stack)-1]] = num
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}

	return res
}

• 时间复杂度：O(n)，每个元素最多进栈出栈一次；
• 空间复杂度：O(n)，用了切片存储链表值和栈，最坏为 O(n)。

➡️ 点击查看 Java 题解

write your code here

相似题目

本文作者: HGNULB

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

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！