496. Next Greater Element I

mono stack + hashmap

T: O(n+m), n is num1, m is nums2

T: O(n+m)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        
        Map<Integer, Integer> map = new HashMap<>(); // <number, next greater element>
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                int now = stack.pop();
                map.put(now, num);
            }
            stack.push(num);
        }
        
        int i = 0;
        for (int num : nums1) {
            res[i++] = map.getOrDefault(num, -1);
        }
        return res;
    }
    
}

/*

[1,3,4,2]
1: 3
3: 4
4: -1
2: -1



[4, 3, 2, 1, 6]

4: 6
3: 6
2: 6
1: 6
6: -1
*/