【LeetCode每日一题】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 。示例 2:

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

提示：

1 <= nums1.length <= nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 104 nums1和nums2中所有整数互不相同 nums1 中的所有整数同样出现在 nums2 中

题解： 暴力做法还是比较好想的，在这里做了一点点小小的优化，可以稍微加速一点，那就是用一个哈希表存储下nums2的数的下标。

//其实就是暴力做法
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> m;
        //存储下标
        for(int i = 0; i < nums2.size(); i++){
            m[nums2[i]] = i; 
        }
        vector<int> ans;
        //找答案，添加
        for(int i = 0; i < nums1.size(); i++){
            bool flag = false;
            for(int j = m[nums1[i]]; j < nums2.size(); j++){
                if(nums2[j] > nums1[i]){
                    ans.push_back(nums2[j]);
                    flag = true;
                    break;
                }
            }
            if(!flag) ans.push_back(-1);
        }
        return ans;
    }
};

题解二：可以采用单调栈将nums2中右边第一个比当前位置数大的位置预处理出来，再在nums1中一一对应查找。时间复杂度是 m+n的

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> m;
        stack<int> stk;
        for(int i = nums2.size() - 1; i >= 0; i--){
            //删掉栈中比当前位置小的数
            while(!stk.empty() && nums2[i] >= stk.top()) stk.pop();
            if(stk.empty()) m[nums2[i]] = -1;
            else m[nums2[i]] = stk.top();
            stk.push(nums2[i]);
        }
        //添加答案
        vector<int> ans;
        for(auto e: nums1){
            ans.push_back(m[e]);
        }
        return ans;
    }
};