力扣-动态规划-496 下一个更大的元素Ⅰ

思路和时间复杂度

1. 思路：题目中的意思为是值相同的情况下的右边第一个最大的元素，所以直接在nums2中寻找下一个最大元素即可，要用map记录一下下标和值，在nums中找到下一个最大值，还要确认当前比较的值是否在num1中
2. 时间复杂度：       

代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size(), -1);
        // 遍历nums2，找到nums2的每一个元素在右边第一个大的元素，然后利用元素值定位nums1，找到下标
        unordered_map<int, int> ump;
        
        for(int i = 0; i < nums1.size(); i++){
            ump[nums1[i]] = i;
        }

        stack<int> st;
        st.push(0);
        for(int i = 1; i < nums2.size(); i++){
            if(nums2[i] > nums2[st.top()] ){
                while(!st.empty() && nums2[i] > nums2[st.top()] ){
                    if(ump.count(nums2[st.top()]) >= 1){
                        int index = ump[nums2[st.top()]];
                        res[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }else{
                st.push(i);
            }
        }

        return res;
    }
};