496. Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. 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.

给你两个数组，第一个数组是第二个的子集，且每个元素都是唯一的。要你求数组一对应位置之后的第一个比他大的数。

嗯嗯，，最容易的想法应该是对于每个位置进行暴力匹配，时间应该是O（ N2），但是仔细想想的话，每个数都是不同的这个大好条件没有用到。

那么反过来思考一下如何？我们之前是去找比他大的元素，那么给定一个元素，我们去找比他小的元素会如何呢？

答案是可以的，而且相当好。我们用一个hashmap去映射元素和对于位置之后第一个比他大的元素。若元素比peek（））要大，简单的pop元素到hashmap中去建立映射关系，最后将这个元素保存到stack的栈顶以恢复降序，如果元素比peek()要小，那么我们把它存放到一个stack的栈顶做新的peek，这样这个stack中的元素是以降序排列的，我们只要pop（）出所有比它小的元素即可。这样的话充分利用了有序性和stack的FILO的性质。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[nums1.length] ;
        for(int i = 0 ;i<nums2.length;i++)
        {  
                    while(!stack.isEmpty()&&stack.peek()<nums2[i])
                    {
                        map.put(stack.pop(),nums2[i]);
                    }
            stack.push(nums2[i]);
        }
         for(int i = 0 ;i<nums1.length;i++)
         {
             result[i]=map.getOrDefault(nums1[i],-1);
         }
        
        return result;
        
    }
}