leetcode_for_rust/cd0496_next_greater_element_i/
mod.rs

1//! Next Greater Element I [leetcode: next_greater_element_i](https://leetcode.com/problems/next-greater-element-i/)
2//!
3//! You are given two arrays **(without duplicates)** `nums1` and `nums2` where `nums1`’s elements are subset of `nums2`. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.
4//!
5//! The Next Greater Number of a number x in `nums1` is the first greater number to its right in `nums2`. If it does not exist, output -1 for this number.
6//!
7//! **Example1:**
8//!
9//! ```
10//! Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
11//! Output: [-1,3,-1]
12//! Explanation:
13//!     For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
14//!     For number 1 in the first array, the next greater number for it in the second array is 3.
15//!     For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
16//! ```
17//!
18//! **Example2:**
19//!
20//! ```
21//! Input: nums1 = [2,4], nums2 = [1,2,3,4].
22//! Output: [3,-1]
23//! Explanation:
24//!     For number 2 in the first array, the next greater number for it in the second array is 3.
25//!     For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
26//! ```
27//!
28//! **Note**
29//!
30//! 1. All elements in `nums1` and `nums2` are unique.
31//! 2. The length of both `nums1` and `nums2` would not exceed 1000.
32//!
33use std::collections::HashMap;
34/// # Solutions
35///
36/// # Approach 1: HashMap
37///
38/// * Time complexity: O(n)
39///
40/// * Space complexity: O(n)
41///
42/// * Runtime: 0ms
43///
44/// Memory: 2.4MB
45///
46/// ```rust
47/// use std::collections::HashMap;
48///
49/// impl Solution {
50///     pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
51///         let mut stack = vec![-1; nums1.len()];
52///         let mut nums_map: HashMap<&i32, usize> = HashMap::new();
53///
54///         for (i, num) in nums2.iter().enumerate() {
55///             nums_map.insert(num, i);
56///         }
57///
58///         for (i, num) in nums1.iter().enumerate() {
59///             for j in *nums_map.get(num).unwrap()..nums2.len() {
60///                 if nums2[j] > *num {
61///                     stack[i] = nums2[j];
62///                     break;
63///                 }
64///             }
65///         }
66///         stack
67///     }
68/// }
69/// ```
70///
71///
72/// # Approach 2: Stack
73///
74/// * Time complexity: O(n)
75///
76/// * Space complexity: O(n)
77///
78/// * Runtime: 0ms
79///
80/// Memory: 2.6MB
81///
82/// ```rust
83/// use std::collections::HashMap;
84///
85/// impl Solution {
86///     pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
87///         let mut nums_map: HashMap<&i32, usize> = HashMap::new();
88///         let mut stack = vec![];
89///         let mut result = vec![-1; nums1.len()];
90///
91///         for (i, num) in nums1.iter().enumerate() {
92///             nums_map.insert(num, i);
93///         }
94///
95///         for num in nums2.into_iter() {
96///             while !stack.is_empty() && *stack.last().unwrap() < num {
97///                 if let Some(val) = nums_map.get(&stack.pop().unwrap()) {
98///                     result[*val] = num;
99///                 }
100///             }
101///             stack.push(num);
102///         }
103///         result
104///     }
105/// }
106/// ```
107///
108pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
109    let mut nums_map: HashMap<&i32, usize> = HashMap::new();
110    let mut stack = vec![];
111    let mut result = vec![-1; nums1.len()];
112
113    for (i, num) in nums1.iter().enumerate() {
114        nums_map.insert(num, i);
115    }
116
117    for num in nums2.into_iter() {
118        while !stack.is_empty() && *stack.last().unwrap() < num {
119            if let Some(val) = nums_map.get(&stack.pop().unwrap()) {
120                result[*val] = num;
121            }
122        }
123        stack.push(num);
124    }
125    result
126}
leetcode_for_rust/cd0496_next_greater_element_i/mod.rs

leetcode_for_rust/cd0496_next_greater_element_i/
mod.rs
