496 Next Greater Element I

496. Next Greater Element I

1. Question

You are given two arrays(without duplicates)nums1andnums2wherenums1’s elements are subset ofnums2. Find all the next greater numbers fornums1's elements in the corresponding places ofnums2.

The Next Greater Number of a numberxinnums1is the first greater number to its right innums2. If it does not exist, output -1 for this number.

Example 1:

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.

Example 2:

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 nums1andnums2are unique.

2. The length of bothnums1andnums2would not exceed 1000.

2. Implementation

思路: 题目已经说明nums1是nums2的子集，所以可以对nums2进行遍历，维护一个单调递减stack, 当栈顶的数小于当前nums2的数时，则nums2是栈顶数的Next Greater Element。同时通过一个HashMap记录每个元素的Next Greater Element即可

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

3. Time & Space Complexity

时间和空间复杂度都为O(n), n为nums2里的元素个数