1019. 链表中的下一个更大节点
给定一个长度为 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^4
1 <= Node.val <= 10^9
解答:
class Solution {
public int[] nextLargerNodes(ListNode head) {
if (head == null) {
return new int[0];
}
// 计算链表长度
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
int[] answer = new int[length];
Stack<Integer> stack = new Stack<>();
int index = 0;
current = head;
//单调栈
while (current != null) {
while (!stack.isEmpty() && current.val > answer[stack.peek()]) {
int idx = stack.pop();
answer[idx] = current.val;
}
stack.push(index);
answer[index]=current.val;
index++;
current = current.next;
}
// 将剩余索引的值设置为 0
while (!stack.isEmpty()) {
answer[stack.pop()] = 0;
}
return answer;
}
}