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

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

题解

基于单调栈的做法，不考虑这道题的链表情况，给定一个表，求每个元素的下一个更大元素都可以用单调栈的做法

逆序遍历这个表，每次遍历一个元素时检查栈，当栈顶元素≤当前元素时循环出栈

• 当出栈到栈顶元素＞当前元素时，此时栈顶元素即为当前元素的下一个更大元素（此时栈顶元素没有被出栈，所以要用peek），然后将当前元素入栈
• 当出栈到栈空时，说明当前元素不存在下一个更大元素

那么唯一的问题就是如何逆序遍历链表了，这里我直接写了一段反转链表来实现

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        int cnt=0;
        ListNode node=head,last=null,next;

        Stack<ListNode> stack=new Stack<ListNode>();
        while(node!=null){
            cnt++;
            next=node.next;
            if(last!=null){
                node.next=last;
            }
            last=node;
            if(next!=null){
                node=next;
            }else{
                head=node;
                break;
            }
        }

        int[] ans=new int[cnt];
        int i=cnt-1;
        node=head;

        while(i>=0){
            while(!stack.isEmpty()&&stack.peek().val<=node.val){
                stack.pop();
            }
            if(stack.isEmpty()){
                ans[i]=0;
            }else{
                ans[i]=stack.peek().val;
            }
            stack.push(node);
            node=node.next;
            i--;
        }
        return ans;
    }
}