下一个更大元素I496

一 题目：

二 思路：

这题其实算法要求进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？ 这里有个提示。
也就说算法要求两个数组都便利一次就解决问题。
那么显然我们可以用单调栈先遍历nums2把每一个元素右侧第一个比自己大的数都记录下来，再遍历num1，这样就找到目标数组了。
那么这里的单调栈是什么概念呢？你可以理解为每一个还没找到比自己大的元素都放进来。那么每一个数其实都是单调递减的了。

三 代码：

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res=new int[nums1.length];

        Stack<Integer> indexStack=new Stack<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!indexStack.isEmpty()&&nums2[i]>nums2[indexStack.peek()]){
                map.put(nums2[indexStack.peek()],nums2[i]);
            }
            indexStack.push(i);
        }

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