Li Kou daily question - day 25 -496 Next larger element I

2022.6.23 Did you brush the questions today ？

---

subject ：

nums1 Middle number x Of Next bigger element Refer to x stay nums2 Corresponding position in On the right side Of first Than x Big elements .

Here are two for you There are no repeating elements Array of nums1 and nums2 , Subscript from 0 Start counting , among nums1 yes nums2 Subset .

For each 0 <= i < nums1.length , Find satisfaction nums1[i] == nums2[j] The subscript j , And in nums2 determine nums2[j] Of Next bigger element . If there is no next larger element , Then the answer to this query is -1 .

Returns a length of nums1.length Array of ans As the answer , Satisfy ans[i] As mentioned above Next bigger element

analysis ：

Given two arrays , for example

num1【1,2,3】,num2【1,2,4,3】, be num1 Of 【1】 Corresponding num2 Of 【2】,num1 Of 2 Corresponding num2 Of 【4】,num1 Of 【3】 No corresponding , Then return 【2,4,-1】

That is, for the elements in array one , We're going to be in the array 2 Find out whether there is an element that satisfies the following conditions

1. stay num2 The next element must be the first element to the right of the element

2. And the element is larger than the element in array one

The idea is to solve by violence , Traversing two arrays , Look for... In the first layer of circulation num1 Value , See if there is an element in the second layer of the loop that meets this requirement .

analysis ：

1. Violent solution

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. Monotonic stack

This class of methods is used to solve the larger type of the next element in the array .

The idea is to use a stack to maintain a stack arranged from small to large , Then insert the data into map in , And then map Insert vector in （ Personally, it is still very difficult ）. If a larger value is encountered during stack insertion , It's about to go out of the stack , This method needs more practice ！

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;
    }
};