题目描述

给定两个 没有重复元素 的数组 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和nums2中所有元素是唯一的。
2. nums1和nums2 的数组大小都不超过1000。

算法思路

单调栈

在LeetCode 739. 每日温度 中介绍了单调栈的用法和具体实现，这道题其实与上面739题比较类似，也是需要找到数组中每个元素下一个更大的元素。因此我们的具体思路也是利用单调栈找到数组nums2中每个元素的下一个更大的数。题目说数组nums1是数组nums2的子集，意思是nums1中的所有元素均在nums2中，但是由于nums1中元素的排列顺序与nums2不同，所以我们要想一个办法找到nums1中的元素在nums2中的映射。所以我们还需要利用哈希表，将nums2中每个元素的值和下一个更大元素作为一个键值对保存在哈希表中。之后当我们遍历nums1中的每个元素时，我们只需要返回该值在nums2中对应的下一个元素更大值。具体步骤如下：

1. 依次遍历每个元素，当栈不空且栈顶元素比当前元素小时，该数作为栈顶元素的下一个更大元素，加入哈希表中，并将栈顶元素弹出。直到栈顶元素大于等于该元素时停止，然后将该元素放入栈中。
2. 此时栈中可能还有元素，这些元素不存在下一个更大的元素，所以根据题意，我们需要依次弹出，并将其哈希值赋为-1.
3. 依次遍历nums1中的每个元素，找到在nums2中该元素的下一个更大值并存入答案数组中。

C++代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> stk;
        unordered_map<int, int> hash; 
        for (int i = 0; i < nums2.size(); i ++)
        {
            while (stk.size() && nums2[stk.top()] < nums2[i]) 
            {
                int j = stk.top();
                stk.pop();
                hash[nums2[j]] = nums2[i];
            }
            stk.push(i);
        }

        while (stk.size())
        {
            int j = stk.top();
            stk.pop();
            hash[nums2[j]] = -1;
        }

        vector<int> res;
        for (auto x : nums1) res.push_back(hash[x]);
        return res;
    }
};