496.下一个更大元素Ⅰ

题目：496.下一个更大元素Ⅰ

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例：

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

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

题解：

方法一：遍历+哈希表
如果直接遍历两个数组来寻找下一个更大元素的话，相当于$ n^2 $的算法，时间复杂度比较高，又因为题目里面说nums1和nums2中的元素互不相同，所以可以用哈希表来做一个加速，首先先遍历nums2数组，把nums2中元素的值和对应的下标放到哈希表中，之后再遍历nums1数组，把找到num2对应的元素，从哈希表中得到下标，之后往后遍历寻找到第一个最大元素后跳出循环，如果没有找到，就给ans中赋值-1

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
	int m = nums1.length,n = nums2.length;
	int[] ans = new int[m];
	HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0;i<n;i++){
        map.put(nums2[i],i);
    }
    for (int i = 0;i<m;i++){
        int x = nums1[i];
        int j = map.get(x);
        for (;j<n;j++){
            if (nums2[j]>x){
                ans[i] = nums2[j];
                break;
            }
        }
        if (ans[i]==0){
        	ans[i] = -1;
        }
    }
    return ans;
}

方法二：单调栈
因为我们找某个数在nums2右边比它大的第一个数，所以我们可以对nums2进行逆序遍历。
我们首先遍历nums2数组，遍历的同时维护一个单调栈，当我们遍历到nums2[i]元素时，我们先将栈顶中比nums2[i]小的元素出栈。出完后有两种结果：

1. 栈为空，说明nums2[i]右边没有比它大的元素。
2. 栈不为空，此时栈顶元素是nums2[i]右边离他最近的元素。
   再利用数组中的元素各不相同，在遍历nums2时，使用哈希表记录每个元素对应的目标值是多少。

   class Solution {
       public int[] nextGreaterElement(int[] nums1, int[] nums2) {
           int n = nums1.length, m = nums2.length;
           Deque<Integer> d = new ArrayDeque<>();
           Map<Integer, Integer> map = new HashMap<>();
           for (int i = m - 1; i >= 0; i--) {
               int x = nums2[i];
               while (!d.isEmpty() && d.peekLast() <= x) d.pollLast();
               map.put(x, d.isEmpty() ? -1 : d.peekLast());
               d.addLast(x);
           }
           int[] ans = new int[n];
           for (int i = 0; i < n; i++) ans[i] = map.get(nums1[i]);
           return ans;
       }
   }