JZX轻语：简

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

发表于2024年06月04日

#链表 #单调栈

一般而言，求解下一个更大元素的题目可以考虑单调栈。在此类题目中，可以使用栈来存储当前右侧还没有更大元素的链表节点(必然单调递减，否则和前提矛盾)。遍历链表节点，如果当前节点的值大于栈顶节点的值，则弹出栈顶节点并设置其结果为当前节点的值，直至栈为空或栈顶节点的值大于当前节点的值。最后将当前节点入栈。

在这里需要注意一点的是，由于遍历完毕前并不清楚链表的长度，在遍历每个节点时，需要先追加一个0作为该节点的初始结果。

class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        stack = []
        ans = []
        idx = 0
        while head:
            ans.append(0)  # 占位, 由于不清楚到底有多少个节点, 先追加一个空的元素
            while stack and stack[-1][0] < head.val:
                ans[stack[-1][1]] = head.val
                stack.pop()
            stack.append((head.val, idx))
            idx += 1
            head = head.next
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/next-greater-node-in-linked-list/