力扣每日一题-第25天-496.下一个更大元素Ⅰ

2022.6.23今天你刷题了吗？

---

题目：

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

分析：

给定两个数组，例如

num1【1，2，3】，num2【1，2，4，3】，则num1的【1】对应num2的【2】，num1的2对应num2的【4】，num1的【3】则无对应，然后返回【2，4，-1】

也就是说对于数组一中的元素，我们要在数组2中去找是否存在一个元素满足下面条件

1.在num2下该必须是元素右方存在第一个一个元素

2.且该元素大于数组一中这个素

思路就是暴力求解，遍历两个数组，在第一层循环中去找num1的值，看第二层循环是否存在一个满足该要求的元素。

解析：

1.暴力求解

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int>vec;
        int flag = 0;
        for (auto i = 0; i < nums1.size(); ++i)
        {
            for (auto j = 0; j < nums2.size(); ++j)
            {
                if (nums1[i] == nums2[j])
                {
                    flag = 1;
                }
                if (flag == 1&&nums1[i]<nums2[j])
                {
                    vec.push_back(nums2[j]);
                    flag = 0;
                    break;
                }
                if (flag == 1 && nums1[i] >= nums2[j]&&j==nums2.size()-1)
                {
                    vec.push_back(-1);
                    flag = 0;
                    break;
                }
            }
        }
        return vec;
    }
};

2.单调栈

该类方法用于解决数组中下一个元素更大类型。

思想就是利用一个栈去维护一个从小到大排列的栈，然后把数据插入map中，再把map插入vector中（个人感觉还是很难）。其中如果在栈插入时遇到更大的值，就要进行出栈，这个方法还要多练！

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> hashmap;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; --i)
        {
            int num = nums2[i];
            while (!st.empty() && num >= st.top())
            {
                st.pop();
            }
            hashmap[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        vector<int>res(nums1.size());
        for (auto i = 0; i < nums1.size(); ++i)
        {
            res[i] = hashmap[nums1[i]];
        }
        return res;
    }
};