栈 496. 下一个更大元素 I

题目描述

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

题目的大概意思是，对比相同元素的下标，从右边找一个比当前元素大的值

1.当时没看懂题目，脑袋有点炸，看了一下题解，当时我就很草了，直接hashmap + 暴力

用map存入 value 与下标，在num1中去num2里面取下标，遍历下标后面的数，两三分钟就写完了

其实用map + 栈可能复杂度会好一点，

把num2每个数都压入栈里面，同时遍历num2元素，当栈不为空，并且当前元素大于 栈里面元素，说明，找到了，循环遍历栈，把比当前元素的栈元素的值全部pop出来，存在map里面，记录 栈元素，当前元素。这样的复杂度明显会比暴力好一点。此思路相等与，2号元素造1号得大值，3号找2号得，2号找到了，顺便看看1号还在不在，在的话顺便把一号弹出，可能大家害怕，当前的值大于1号值却小与2号，不存在的，当有这种情况，早就在2号时候，1号被弹出了

public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] num = new int[nums1.length];
        HashMap<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
<pre><code>    for (int i = 0; i &lt; nums2.length; i++) {
        while (stack.size() &gt; 0 &amp;&amp; stack.peek() &lt; nums2[i]) {
           map.put(stack.pop(),nums2[i]);
        }
        stack.push(nums2[i]);
    }

    for (int i = 0; i &lt; nums1.length; i++) {
        num[i] = map.getOrDefault(nums1[i],-1);
    }

    return num;
}