刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/next-greater-node-in-linked-list
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个更大节点的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。

返回一个整数数组answer，其中answer[i]是第i个节点(从1开始)的下一个更大的节点的值。如果第i个节点没有下一个更大的节点，设置answer[i] = 0。

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]

示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

提示：

• 链表中节点数为 n
• 1 <= n <= 104
• 1 <= Node.val <= 109

思路

这个题还是比较简单的
1、因为很明显我们不大可能接受多次扫描链表，只有一遍扫描的情况下，元素很可能是需要一个等待下一个比他大的结果的状态
2、找到第一个比他大的结果时即可完成对于本节点的处理，再接着去处理下一个节点
这个思路下很容易想到栈这个数据结构，先进后出，一个个节点遍历过程中不断的去比较，遇到严格大的下一个数则弹出

写完之后发现跟题解好像，哈哈

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func nextLargerNodes(head *ListNode) []int {
	if head.Next == nil {
		return []int{0}
	}
	stack := make([][]int, 0)
	result := make([]int, 0)

	for ; head != nil; head = head.Next {
		result = append(result, 0)
		// 检查是否大于当前栈顶值，大于则弹出，赋值结果数组
		for len(stack) > 0 && stack[len(stack)-1][0] < head.Val {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result[top[1]] = head.Val
		}
		stack = append(stack, []int{head.Val, len(result) - 1})
		// 当前值压入栈顶
	}
	return result
}