题目

• 概述：给定一个链表，要你求该链表每个元素的下一更大元素，如果不存在下一个更大元素则下一个更大元素为0

• 输入：链表的头节点，链表长度范围[0, 10000]，链表值范围[1, 10^9]

• 输出：链表每个元素的下一更大元素

• 出处：https://leetcode-cn.com/problems/next-greater-node-in-linked-list/

思路

• 求下一更大节点需要比较当前节点和下一个节点的值的大小，如果当前节点的值大于下一个节点，那么就需要比较当前节点和下一个节点的下一个更大节点的值的大小，所以需要保存当前节点的信息，因此考虑使用栈实现

• 构造数据结构Node，包含节点数据val以及节点索引index

• 遍历链表：

  1. 若栈为空，将链表当前节点和索引构造数据结构Node入栈，并移动到下一个节点
  2. 比较栈顶结点和链表当前节点的值的大小：
     1. 栈顶结点的值 < 链表当前节点的值 => 得出栈顶结点的下一个更大元素，将栈顶结点出栈
     2. 栈顶结点的值 >= 链表当前节点的值 => 将链表当前节点和索引构造数据结构Node入栈，并移动到下一个节点

• 若栈中仍存在元素，则将栈中所有元素出栈，并置每个元素的下一个更大元素为0

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public int[] nextLargerNodes(ListNode head) {
        int[] temp = new int[10000];
        int index = 0;
        LinkedList<Node> stack = new LinkedList<>();
        Node top;
        ListNode cur = head;
        
        while (cur != null) {
            if (stack.isEmpty()) {
                stack.push(new Node(cur.val, index++));
                cur = cur.next;
            }
            
            if (cur == null) {
                break;
            }
            
            top = stack.peek();
            if (top.val < cur.val) {
                temp[top.index] = cur.val;
                stack.pop();
            } else {
                stack.push(new Node(cur.val, index++));
                cur = cur.next;
            }
        }
        
        while (!stack.isEmpty()) {
            temp[stack.pop().index] = 0;
        }
        
        int[] result = new int[index];
        for (int i = 0; i < index; ++i) {
            result[i] = temp[i];
        }
        
        return result;
    }
    
    private class Node {
        int val;
        int index;
        
        Node(int val, int index) {
            this.val = val;
            this.index = index;
        }
    }
}