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.

这个题有点说法，首先要记录nums1中的数和index，放在一个map里。然后遍历nums2，同时维护一个递减的stack，对于nums2中的元素，和stack中的栈顶元素对比，如果比栈顶元素大，则说明对于这个栈顶元素来说，当前的元素就是下一个更大的值，把栈顶元素pop出来，继续查看下一个栈顶元素，直到栈顶元素大于当前的nums2的元素，push到stack中

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0)
            return new int[0];

        int[] res = new int[nums1.length];
        for(int i = 0; i < res.length; i++)
            res[i] = -1;

        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < nums2.length; i++) {
            while(stack.size() > 0 && stack.peek() <= nums2[i]) {
                int last = stack.pop();
                if(map.containsKey(last)) {
                    res[map.get(last)] = nums2[i];
                }
            }

            stack.push(nums2[i]);
        }

        return res;
    }
}