leetcode503下一个更大元素||

亦凉 2022-10-05 06:46 156阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
思路：

1.  这个也是**单向栈**，栈中存编号，记录每一个比栈顶代表的元素小的编号，弹出栈中每个比当前值要小的编号。
2.  **循环的处理，直接将数组复制一倍**，这个思想非常妙。
3.  注意每次弹出之前都要判断栈是否为空，vector当栈用的时候非常容易忘记

代码

vector<int> nextGreaterElements(vector<int>& nums){ 
        int len = nums.size();
        if(len==0){ 
            vector<int> res;
            return res;
        }
        vector<int> temp(nums);
        nums.insert(nums.end(),temp.begin(),temp.end());
        if(len==1){ 
            vector<int> res;
            res.push_back(-1);
            return res;
        }
        int i,j;
        vector<int> res(len*2,-1);
        cout<<endl;
        vector<int> s;
        for(i=0;i<len*2;i++)
        { 
            if(s.empty()){ 
               s.push_back(i);
            }
            else{ 
                if(nums[i]<=nums[s.back()])
                    s.push_back(i);
                else
                    { 
                        while(!s.empty()&&nums[i]>nums[s.back()]){ 
                            res[s.back()]=nums[i];
                            s.pop_back();//注意在弹出的时候需要判断栈是否为空
                        }
                        s.push_back(i);
                    }
            }
        }
        vector<int> r_res(res.begin(),res.begin()+len);
        return r_res;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221005/0fe924aa57694cd5b37a154d0ce0dbe2.png