【Leetcode Daily】1019链表中的下一个更大的节点

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个链表，现在对于每个节点，要找下一个比它更大的节点的值。

思路分享

• 两个关键点：1. 是严格更大，相同不算；2. 根据评论区所言，如果感到不知所措，就可以尝试转成数组来思考。

• 本题可以通过倒序遍历+单调栈来解决，单调栈存储每个节点的下一个更大的值（没有就用 0），倒序遍历就是单调栈，让遍历每一个值的时候，可以 O(1) 判断其右侧还有没的更大值。

  https://leetcode.cn/problems/next-greater-node-in-linked-list/solutions/2217563/tu-jie-dan-diao-zhan-liang-chong-fang-fa-v9ab/

代码解答（强烈建议自行解答后再看）

• 参考题解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        head = self.reverse(head)
        ans = []
        st = []
        while head:
            while st and st[-1] <= head.val:
                st.pop()
            ans.append(st[-1] if st else 0)
            st.append(head.val)
            head = head.next
        return ans[::-1]