1019：链表中的下一个更大节点（1570 分）

力扣第 130 场周赛第 3 题

题目

给定一个长度为 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

分析

类似 0739 ，可以用单调栈解决。事先不知道链表长度，因此边遍历边维护结果数组即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def nextLargerNodes(self, head: ListNode) -> List[int]:
	res, stack, i = [], [], 0
	while head:
		while stack and stack[-1][1] < head.val:
			res[stack.pop()[0]] = head.val
		stack.append((i, head.val))
		res.append(0)
		head = head.next
		i += 1
	return res

324 ms