【LeetCode每日一题: 1019. 链表中的下一个更大节点 | 单调栈 】

🍎作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🍎座右铭：人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯🎯

题目链接

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

题目描述

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

看看官方给定的测试用例。

提示：

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

求解思路&实现代码&运行结果

单调栈

求解思路

• 问1:首先我们来补充一个知识点，什么是单调栈？
• 我们都知道栈，那什么是单调栈呢？我们可以从单调入手，所谓单调，就是我们元素的值保持递增，或者递减的性质。

• 问2:为什么要使用单调栈呢？
• 通过读取题目的意思我们可以知道，我们想要求得链表中大于当前节点值的下一个更大的节点，那么我我们就可以来维护一个单调递减的栈，也就是从我们的栈底到栈顶中的元素是单调递减的，我们可以使用单调栈快速的找到大于当前元素的下一个更大的节点是什么。

• 问3:为什么要使用单调栈呢？
• 通过读取题目的意思我们可以知道，我们想要求得链表中大于当前节点值的下一个更大的节点，那么我我们就可以来维护一个单调递减的栈，也就是从我们的栈底到栈顶中的元素是单调递减的，我们可以使用单调栈快速的找到大于当前元素的下一个更大的节点是什么。

• 问4:怎么实现呢？
• 因为最后结果需要我们收集答案，所以我们首先我们可以先遍历链表，得到其长度；
• 开辟一个链表长度的数组，用于最后结果的收集；
• 然后我们去维护一个单调栈，注意:单调栈中此时维护的是[数组元素，数组下标]，如果此时栈顶的元素是小于当前遍历到链表节点的值，那么我们直接弹出栈顶的数组，并且更新此时该栈顶的下一个更大的元素。
• 如果单调栈中的元素保持单调递减，我们直接添加进行维护即可。

• 问5:单调栈中为什么需要维护一个数组呢？
  因为我们需要收集结果，如果说只是找到下一个更大节点的值，我们只需要维护节点的值就可以了，但是题目最后的要求是需要我们找到大于每一个位置下一个更大的节点，所以说我们还需要一个记录下标位置的值。

• 问6:单调栈中可以维护一个元素的下标吗？
• 当然可以，没有问题的，只是在实现代码的一些细节地方需要注意[最后特判一下栈中元素不为空的情况]，总求解思路是一致的。

实现代码

注意:思路确定了，实现的语言只是一个工具，此处我们使用Java，感兴趣的同学可以使用其它的编程语言实现。

/*** 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) {int n=0;ListNode cur=head;while(cur!=null){cur=cur.next;n++;}int[] res=new int[n];Deque<int[]> queue=new LinkedList<>();cur=head;int i=0;while(cur!=null){while(!queue.isEmpty()&&queue.peek()[0]<cur.val){res[queue.pop()[1]]=cur.val;}queue.push(new int[]{cur.val,i++});cur=cur.next;}return res;}
}

运行结果

单调栈加强练习

如果只是做了一道单调栈的题目，想必大家也没有过瘾，一个知识点怎么也要做好多题目才能熟练掌握，那么我就给大家罗列了LeetCode上常考的单调栈的题目，感兴趣的同学可以做一做。

• 496. 下一个更大元素 I
• 503. 下一个更大元素 II
• 2454. 下一个更大元素 IV
• 456. 132 模式
• 739. 每日温度
• 901. 股票价格跨度
• 1124. 表现良好的最长时间段
• 1475. 商品折扣后的最终价格
• 2289. 使数组按非递减顺序排列

共勉

最后，我想送给大家一句一直激励我的座右铭，希望可以与大家共勉！