LeetCode.496.下一个更大的元素(C++)

题目描述：


题解思路：
方法一：暴力解法

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
        //暴力解法，遍历两数组
        int length1=nums1.size();
        int length2=nums2.size();
        vector m(length1);
        for(int i=0;i=length2?-1:nums2[k];
        }
        return m;
    }
};

方法二:单调栈+哈希表

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
        //单调栈+哈希表：今后遇见类似于下一个更大元素的时候直接运用单调栈
        //先定义单调栈和哈希表
        unordered_map hashmap;//定义的哈希表是将nums1中元素对应nums2中下一个更大元素存储起来
        stack st;
        for(int i=nums2.size()-1;i>=0;i--)//从后向前遍历数组nums2
        {
            int num=nums2[i];
            while(!st.empty()&&num>=st.top())//当栈中不为空并且当前遍历的数组>栈顶元素时，将栈中当前元素出栈
            {
                st.pop();//出栈
            }
            hashmap[num]=st.empty()?-1:st.top();//当栈为空时，说明栈中没有比元素num更大的元素(-1代表没有比num更大的元素；当栈不为空时，说明栈中栈顶元素比当前元素num更大。请结合代码自己推一推)
            st.push(num);//将满足条件的num入栈
        }
        vector m(nums1.size());
        for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5717966.html