NC354 下一个更大的数(二)

单调栈+断环为链

//定义一个手写栈，由一个数组和一个top指针组成
 int skt[100005],top;
 class Solution {
public: 
    vector<int> nextBigger(vector<int>& nums) {
        int n=nums.size();
        //定义一个用于存答案的vector
        vector<int> ans(n);
        //断环为链，可以通过%n，比较方便
        //由于要向右找第一个大于本身的数,所以可以逆向遍历维护一个单调栈
        for(int i=2*n-1;i>=0;i--){
            //只要栈不为空并且栈顶的元素对应的值小于等于需要入栈的元素的值，就让栈顶出栈
            while(top&&skt[top]<=nums[i%n]) top--;
            //由于最后只需要得到前n个数对应的右边第一个大于本身的元素，所以只需要i<n
            if(i<n){
                //如果栈不为空，就将栈顶记入答案中
                if(top) ans[i]=skt[top];
                //否则，就表示右边不存在一个大于的元素
                else ans[i]=-1;
            }
            //入栈
            skt[++top]=nums[i%n];
        }
        return ans;
    }
};