We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.
Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.
Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).
Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
Example 1:
Input: [2,1,5] Output: [5,5,0]
Example 2:
Input: [2,7,4,3,5] Output: [7,0,5,5,0]
Example 3:
Input: [1,7,5,1,9,2,5,1] Output: [7,9,9,9,0,5,0,0]
Note:
1 <= node.val <= 10^9 for each node in the linked list.[0, 10000].struct Solution;
use rustgym_util::*;
impl Solution {
fn next_larger_nodes(mut head: ListLink) -> Vec<i32> {
let mut nodes = vec![];
while let Some(node) = head {
nodes.push(node.val);
head = node.next;
}
let n = nodes.len();
let mut stack: Vec<usize> = vec![];
let mut res = vec![0; n];
for i in 0..n {
while let Some(j) = stack.pop() {
if nodes[j] < nodes[i] {
res[j] = nodes[i];
} else {
stack.push(j);
break;
}
}
stack.push(i);
}
res
}
}
#[test]
fn test() {
let head = list!(2, 1, 5);
let res = vec![5, 5, 0];
assert_eq!(Solution::next_larger_nodes(head), res);
let head = list!(2, 7, 4, 3, 5);
let res = vec![7, 0, 5, 5, 0];
assert_eq!(Solution::next_larger_nodes(head), res);
let head = list!(1, 7, 5, 1, 9, 2, 5, 1);
let res = vec![7, 9, 9, 9, 0, 5, 0, 0];
assert_eq!(Solution::next_larger_nodes(head), res);
}