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 nums1 and nums2 are unique.
2. The length of both nums1 and nums2 would not exceed 1000.

Solution 1: native solution O(n*m)

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        if(findNums == null || nums == null) {
            return null;
        }

        int[] result = new int[findNums.length];

        for(int i = 0; i < findNums.length; i++) {
            result[i] = -1;
            boolean found = false;
            for(int j = 0; j < nums.length; j++) {
                if(findNums[i] == nums[j]) {
                    found = true;
                } else if (nums[j] > findNums[i] && found) {
                    result[i] = nums[j];
                    break;
                }
            }
        }
        return result;
    }
}

Solution 2:

实质是找每个数的next greater number, 所以只要遍历一遍数组，同时维护一个单调递减的stack， 把当前数跟 stack top 比较， if > top， 则是 stack top 的next greater number, 并把<number, nextGreater> 存起来。一直拿当前的num 跟 top 比，直到top > num

然后当前num pushed to stack.

O(n) complexity, O(n) space complexity, trade off time with space

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        // find the next greater number for each element in nums
        // decreasing sub-array ( stack)
        if (findNums == null || nums == null) {
            return null;
        }

        Map<Integer,Integer> nextGreater = new HashMap<Integer,Integer>();
        int[] result = new int[findNums.length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for(int num : nums) {
            while( !stack.isEmpty() && stack.peekFirst() < num) {
                nextGreater.put(stack.removeFirst(), num);
            }
            stack.addFirst(num);
        }

        for(int i = 0; i < findNums.length; i++) {
            Integer greater = nextGreater.get(findNums[i]);
            if (greater == null) {
                result[i] = -1;
            } else {
                result[i] = greater;
            }
        }

        return result;
    }
}