发表于 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 题目链接