LeetCode_单调栈_中等_1019.链表中的下一个更大节点

末蓝、 2024-03-24 17:16 28阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**  
![在这里插入图片描述][46ef0048dcb646c08f7411a1a7b50de0.png]

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

**示例 2：**  
![在这里插入图片描述][ef04c8c92d854d2482f428376560588c.png]  
输入：head = \[2,7,4,3,5\]  
输出：\[7,0,5,5,0\]

**提示：**  
链表中节点数为 n  
1 <= n <= 104  
1 <= Node.val <= 109

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

## 2.思路 ##

（1）单调栈

相关题目：  
[LeetCode\_单调栈\_中等\_739.每日温度][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 的数组，存储结点序号以及对应的 val
            Deque<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;
        }
    }

[46ef0048dcb646c08f7411a1a7b50de0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9d692a34bd4e43fb8a2a2fe34fc0e079.png
[ef04c8c92d854d2482f428376560588c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9a6ab39b0da34aea8e5785e00273c64a.png
[LeetCode_739.]: https://blog.csdn.net/weixin_43004044/article/details/125011061