1.题目

题目地址(496. 下一个更大元素 I - 力扣（LeetCode）)

https://leetcode.cn/problems/next-greater-element-i/

题目描述

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] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

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

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

2.题解

2.1 暴力解决

思路

先找到匹配的数索引位置，再从他后面开始找第一个大于这个元素的数位置

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<int> ans;
        for(int i = 0; i < m ; i++){
            // 找到nums2对应num1数组中元素的那个元素位置（方便从下一个位置开始寻找更大元素）
            int j = 0;
            while(j < n && nums1[i] != nums2[j]){
                j++;
            }
            int k = j + 1;
            while(k < n  && nums2[k] < nums2[j]){
                k++;
            }
            int num = k < n ? nums2[k] : -1;
            ans.push_back(num);
        }
        return ans;
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(n)\)

2.2 单调栈

思路

这里我们有两个问题：
1.如何快速获得nums2中元素右侧下一个更大元素
2.如何存储这个更大元素索引，让我们不需要对于每个nums1元素都需要遍历一次nums2,而是直接以O(1)时间复杂度找到对应更大元素

第二个问题比较好解决，由于题目有说明nums2中元素并不重复，如果我们能找到nums2中每个元素的下一个更大元素，使用哈希表分别存储该元素和该元素的下一个更大元素即可，之后遍历nums1直接使用哈希表即可

问题来到如何找到nums2中每一个元素的下一个更大元素？
答案是使用单调栈：
1.我们先来看一下单调栈的定义：从上到下依次递减，如果新入元素大于栈顶元素，则需要弹出栈顶元素直到新入元素小于栈顶元素
2.我们来思考一下：如果我们倒序遍历nums2数组，并维护一个单调栈，每次有一个新入元素就进行大小判断，始终满足从上到下递增的元素
这里我们就可以举一个例子，比如一个元素，我们要找到他下一个更大元素，首先跟单调栈进行判断，
2.1 如果小于该数，说明不是它的下一个更大元素，而对于更左边的元素来说，他的下一个更大元素，只有可能是这个更大的元素，而不是当前栈中那个偏小的元素（例如prev = 1, curr = 5, next = 3， 我们下一次找prev的更大元素只有可能摘掉curr，而不会找到next），所以这里就可以弹出next了；
2.2 如果大于该数，由于单调栈是先入后出，但是我们遍历nums2数组是倒序遍历，所以这里这个更大元素是当前最接近当前元素的更大元素，我们可以将这个元素和其下一个更大元素记录到哈希表，然后结束本次操作
2.3 最后不要忘记将该元素压入单调栈，完成本次入栈操作！

代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<int> ans;
        stack<int> stk;
        unordered_map<int, int> mp;
        for(int i = n - 1; i >= 0; i--){
            int num = nums2[i];
            while(!stk.empty() && num > stk.top()){
                stk.pop();
            }
            mp.emplace(num, stk.empty()?-1:stk.top());
            stk.push(num);
        }

        for(int i = 0; i < m; i++){
            ans.push_back(mp[nums1[i]]);
        }
        return ans;
    }
};