496. Next Greater Element I.md

本题思路：

1. 由于数组的元素是唯一的，构建 nums2 各个元素与其对应的右侧更大值的映射
   1. 单调栈构建
2. 遍历 nums1 , 依次填充res

class Solution {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        //思路：nums2 的元素 映射到 下标

        Deque<Integer> stack=new LinkedList<>();

        Map<Integer,Integer> elem_nextBiggerIdx=new HashMap<>();

        for(int i=0;i<nums2.length;i++){

            while(!stack.isEmpty()&&nums2[i]>nums2[stack.peekLast()]){

                int poll=stack.pollLast();

                elem_nextBiggerIdx.put(nums2[poll],nums2[i]);

            }

            stack.addLast(i);

        }

        while(!stack.isEmpty()){//剩余的元素后续没有最大值

            int poll=stack.pollLast();

            elem_nextBiggerIdx.put(nums2[poll],-1);

        }

        int n=nums1.length;

        int[] res=new int[n];

        for(int i=0;i<n;i++){

            res[i]=elem_nextBiggerIdx.get(nums1[i]);

        }

        return res;

    }

}