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