1.题目

给定一个长度为 n 的链表 head。对于列表中的每个节点，查找下一个更大节点的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点（从 1 开始）的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0。

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]

示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

提示：
链表中节点数为 n
1 <= n <= 10⁴
1 <= Node.val <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-node-in-linked-list

2.思路

（1）单调栈

相关题目：
LeetCode_单调栈_中等_739.每日温度

3.代码实现（Java）

//思路1————单调栈
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public int[] nextLargerNodes(ListNode head) {List<Integer> res = new ArrayList<>();//栈中的元素是一个长度为 2 的数组，存储结点序号以及对应的 valDeque<int[]> stack = new ArrayDeque<>();ListNode cur = head;int index = -1;while (cur != null) {index++;res.add(0);while (!stack.isEmpty() && stack.peek()[0] < cur.val) {res.set(stack.pop()[1], cur.val);}stack.push(new int[]{cur.val, index});cur = cur.next;}int size = res.size();int[] arr = new int[size];for (int i = 0; i < size; i++) {arr[i] = res.get(i);}return arr;}
}