Function leetcode_for_rust::cd0496_next_greater_element_i::next_greater_element

pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32>

Solutions

Approach 1: HashMap

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 0ms

Memory: 2.4MB

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

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
    }
}