题目链接
题目描述
给定一个长度为 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;
}
}
运行结果
单调栈加强练习
- 496. 下一个更大元素 I
- 503. 下一个更大元素 II
- 2454. 下一个更大元素 IV
- 456. 132 模式
- 739. 每日温度
- 901. 股票价格跨度
- 1124. 表现良好的最长时间段
- 1475. 商品折扣后的最终价格
- 2289. 使数组按非递减顺序排列
共勉
最后，我想送给大家一句一直激励我的座右铭，希望可以与大家共勉！