496. 下一个更大元素 I

题目思路：逆序遍历 nums2，在此过程维护单调栈（单调递增），具体过程如下：

• 补充说明：一般情况下，单调栈中我们存储的是元素下标。
• 给定示例 nums2 = {1, 3, 4, 2}
• 对于 nums2[3]=2，当前单调栈为空，则nums2[3]右侧不存在比它更大的数字，这结果利用map存储，即存储<nums2[3], -1>，同时把nums2[3]入栈。
• 对于 nums2[2]=4，当前单调栈为{2}，如果栈不为空且栈顶元素，同时把nums2[2]`入栈。
• 对于 nums2[1]=3，当前单调栈为{4}，当前栈顶元素>nums[i]，存储<nums2[1], 栈顶元素(4)>，同时把nums2[1]入栈。
• 对于 nums2[0]=1，当前单调栈为{3, 4}，当前栈顶元素>nums[i]，存储<nums2[0], 栈顶元素(3)>，同时把nums2[0]入栈。

注：倒序遍历的原因是我们要寻找右侧的第一个更大元素（相较于自身而言），所以倒序遍历正好满足了这个要求。
上述过程已经处理完了nums2中每一个元素的下一个更大元素，因为，我们只需要遍历nums1，利用map直接获取结果即可。

• 时间复杂度：O(len2 + len1)

• 空间复杂度：O(len2 + len1)

  class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new LinkedList<>();
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] ans = new int[len1];
        for(int i = len2 - 1; i >= 0; i--){
            while(!stack.isEmpty() && nums2[stack.peek()] < nums2[i]){
                stack.pop();
            }
            map.put(nums2[i], stack.isEmpty() ? -1 : nums2[stack.peek()]);
            stack.push(i);
        }
        for(int i = 0; i < len1; i++){
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }
  }