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

示例:

输入: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 。

思路

解法一:

暴力法

  1. 遍历循环 nums1,直至找到 nums2 中相等的数;
  2. 继续向后寻找更大的数,若没有找到,则返回 -1,否则返回找到的数。
class Solution
{
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        int m = nums1.size();
        int n = nums2.size();

        vector<int> res(m);
        for (int i = 0; i < m; i++)
        {
            int j = 0;
            while (j < n && nums2[j] != nums1[i])
            { // 找到num2中相等的数
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j])
            { // 向后寻找
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1; // k<n 代表找到,否则k=n没找到
        }
        return res;
    }
};

思路

解法二:

使用单调栈求解

  1. 倒序遍历 nums2,并用单调栈中维护当前位置右边的更大的元素列表,从栈底到栈顶的元素是单调递减的;
  2. 每次我们移动到数组中一个新的位置 i,就将当前单调栈中所有小于 nums2[i]的元素弹出单调栈;
  3. 当前位置右边的第一个更大的元素即为栈顶元素,如果栈为空则说明当前位置右边没有更大的元素,将元素存到map中;
  4. 每次循环将位置 i 的元素入栈。
class Solution
{
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        unordered_map<int, int> hashmap;
        stack<int> stk;
        int m = nums1.size();
        int n = nums2.size();

        for (int i = n - 1; i >= 0; --i)
        {
            int num = nums2[i];
            while (!stk.empty() && num >= stk.top()) {
                stk.pop();
            }
            hashmap[num] = stk.empty() ? -1 : stk.top();
            stk.push(num);
        }
        vector<int> res(m);

        for (int i = 0; i < m; ++i) {
            res[i] = hashmap[nums1[i]];
        }
        
        return res;
    }
};