next-greater-node-in-linked-list

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given the <code>head</code> of a linked list with <code>n</code> nodes.

For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.

Return an integer array <code>answer</code> where <code>answer[i]</code> is the value of the next greater node of the <code>ith</code> node (1-indexed). If the <code>ith</code> node does not have a next greater node, set <code>answer[i] = 0</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext1.jpg" style="width: 304px; height: 133px;" />
<pre>
Input: head = [2,1,5]
Output: [5,5,0]
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext2.jpg" style="width: 500px; height: 113px;" />
<pre>
Input: head = [2,7,4,3,5]
Output: [7,0,5,5,0]
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the list is <code>n</code>.</li>
	<li><code>1 &lt;= n &lt;= 104</code></li>
	<li><code>1 &lt;= Node.val &lt;= 109</code></li>
</ul>

nextLargerNodes

Next Greater Node In Linked List

Stack

Array

Linked List

Monotonic Stack

给定一个长度为&nbsp;<code>n</code>&nbsp;的链表&nbsp;<code>head</code>

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

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

&nbsp;

示例 1：

<img src="https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext1.jpg" />

<pre>
输入：head = [2,1,5]
输出：[5,5,0]
</pre>

示例 2：

<img src="https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext2.jpg" />

<pre>
输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]
</pre>

&nbsp;

提示：

<ul>
	<li>链表中节点数为&nbsp;<code>n</code></li>
	<li><code>1 &lt;= n &lt;= 104</code></li>
	<li><code>1 &lt;= Node.val &lt;= 109</code></li>
</ul>