We first initialize a stack, and then iterate over the nums2 vector. When the top element of the stack is less than the current element we visit in nums2, we pop the top element out, and insert it to our hash table, where key is the top element and the value is the current element in nums2.
Then we iterate over the nums1 vector, if the element we visit is appeared in the lookup table, we push the value in out result, otherwise we push -1.
impl Solution {
pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
let mut table = std::collections::HashMap::new();
let mut stack = vec![];
for n in nums2.iter() {
while let Some(top) = stack.last() {
if n > top {
table.insert(*top, *n);
stack.pop();
} else {
break;
}
}
stack.push(*n);
}
stack.clear();
for n in nums1.iter() {
match table.get(n) {
Some(greater) => stack.push(*greater),
None => stack.push(-1),
}
}
stack
}
}
Practice Dates
Description
Link: https://leetcode.com/problems/next-greater-element-i/description/
Solution
We first initialize a stack, and then iterate over the
nums2
vector. When the top element of the stack is less than the current element we visit innums2
, we pop the top element out, and insert it to our hash table, where key is the top element and the value is the current element innums2
.Then we iterate over the
nums1
vector, if the element we visit is appeared in the lookup table, we push the value in out result, otherwise we push -1.Performance
Time complexity: