力扣-496题下一个更大元素 I（C++）- 单调栈+有价值

谁借莪１个温暖的怀抱￠ 2023-01-24 04:27 25阅读 0赞

题目链接：[https://leetcode-cn.com/problems/next-greater-element-i/][https_leetcode-cn.com_problems_next-greater-element-i]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][2021071623321993.png]  
法一：笨方法

class Solution {
        
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        
            vector<int> result;
            unordered_map<int,int> hash;//用来装nums2,key:数值，value:位置
    
            int pos=0;
            for(auto e:nums2){
        
                hash[e]=pos++;
            }
    
            for(auto e:nums1){
        
                int pos=hash[e],i;
                for(i=pos;i<nums2.size();i++){
        
                    if(nums2[i]>e){
        
                        result.push_back(nums2[i]);
                        break;
                    }
                }
                if(i==nums2.size()) result.push_back(-1);
    
            }
    
            return result;
        }
    };

法二：单调栈

class Solution {
        
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        
            //单调栈
            //step1：先找出nums2的每个对应的右侧最大值
            //step2：再遍历nums1得到最后的result
            stack<int> stk;
            vector<int> vtr(nums2.size());
            for(int i=nums2.size()-1;i>=0;--i){
        
                int x=nums2[i];
                while(stk.size()&&x>=stk.top()) stk.pop();//当栈是非空的，并且当前元素大于栈顶元素，则将栈顶元素删掉
                if(stk.empty()) vtr[i]=-1;//栈空，则说明没有元素比当前值大，当前位置标记为-1
                else vtr[i]=stk.top();//否则，赋为栈顶元素
                stk.push(x);//将数放入栈中
            }
    
            unordered_map<int,int> umap;
            for(int i=0;i<nums2.size();++i)
                umap[nums2[i]]=i;
            vector<int> result;
            for(auto e:nums1)
                result.push_back(vtr[umap[e]]);
            
            return result;
        }
    };

[https_leetcode-cn.com_problems_next-greater-element-i]: https://leetcode-cn.com/problems/next-greater-element-i/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221004/f9fd106d3a82457eafda59892c6b10d0.png
[2021071623321993.png]: /images/20221004/e6c134b34ad74f9784aad3ac447c5ca2.png