136、LeetCode-496.下一个更大元素Ⅰ

题目：

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-i

思路：

单调栈：可以在栈中存储下标；也可以存储数值！

本题使用单调栈按照每日温度的方式处理nums2的数据；nums1的值都能在nums2中找到

使用哈希表存储num1的数值和下标，可以在O(1)的时间复杂度中按照数值找到下标进行结果数组的更新；

主体是nums2；nums1看似是主要的，其实只是确定下标位置

代码：

1）暴力解法：时间复杂度为O(N^2)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len = nums1.length;
        int[] res = new int[len];//作为结果集返回
        for(int i = 0;i < len;i++){
            res[i] = -1;//先赋值为-1
        }
 
        for(int i = 0;i < len;i++){
            for(int j = 0;j < nums2.length;j++){
                if(nums1[i] == nums2[j]){
                    j++;//先j++往后移动一位
                    while(j < nums2.length && nums2[j] < nums1[i]){
                        j++;
                    }
                    if(j >= nums2.length) break;
                    else if(j < nums2.length && nums2[j] > nums1[i]){
                        res[i] = nums2[j];//更新之后不用继续！
                        break;
                    }
                }
            }
        }
        return res;
    }
}

2）单调栈 + 哈希表

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //单调栈 + map；存到map里是为了在O(1)的时间复杂度中找到；
        //整体的逻辑还是在nums2中，只是结果要更新在nums1中
        int l1 = nums1.length;
        int l2 = nums2.length;
        int[] res = new int[l1];//结果数组
        Arrays.fill(res,-1);
 
        Stack stack = new Stack<>();//构造单调栈
        HashMap map = new HashMap<>();
        for(int i = 0;i < l1;i++){
            map.put(nums1[i],i);//为了O1时间复杂度找到下标
        }
        //所有的元素都必然入了一次栈
        for(int i = 0;i < l2;i++){
            while(!stack.isEmpty() && nums2[i] > stack.peek()){
                int num = stack.pop();
                if(map.containsKey(num)){
                    res[map.get(num)] = nums2[i];
                }
            }
            stack.push(nums2[i]);
        }
        return res;
    }
}