503下一个更大的数II

下面是题目给出的代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
    }
};

我给出 两种解法，栈及其优化，BF

栈

因为我在1019链表中下一个更大的数 中介绍过了这种方法

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int tot = nums.size();
        //因为这个数组是可循环的，我们不妨直接拉长一倍
        for(int i = 0;i<tot;i++)
        {
            nums.push_back(nums[i]);
        }
        stack<int>s;
        //随后再每个遍历，很傻逼吧？确实！
        for (int i = (int)nums.size() - 1; i >= 0; --i)
        {
            int cur = nums.at(i); //先暂存当前元素
            while (!s.empty() && cur >= s.top())
             //注意: 等于号不能少 等于时也需要出栈 这里是找严格大于的数
            {
                s.pop();  //淘汰小的 留下更大的
            }
            nums.at(i) = (s.empty() ? -1 : s.top()); //栈空 右边没有更大的
            s.push(cur);
        }
        //随后resize一下
         nums.resize(tot);
        return nums;
    }
};

栈优化

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st;
        //不用扩充nums，而是把i双倍，并用nums[i%n]实现循环效果
        for (int i = 0; i < 2 * n; ++i) {
            int num = nums[i % n];
            //如果栈非空并且栈顶<num,那么应该在res中修改
            while (!st.empty() && nums[st.top()] < num) {
                res[st.top()] = num; 
                //一旦给栈顶所对应的元素，就让他出栈
                st.pop();
            }
            //把st作为标记栈
            if (i < n) st.push(i);
        }
        return res;
    }
};

BF

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int tot = nums.size();
        vector<int>res;
        for(int i = 0;i<tot;i++)
        {
            nums.push_back(nums[i]);
            res.push_back(nums[i]);
        }
        stack<int>s;
        
        for(int i=tot-1;i>=0;--i)
        {
            int max=-1;
            //每一次都遍历后面tot个数，一旦找到就break;
            for(int j=i+1;j<=i+tot;j++)
            {
                if(nums[j]>nums[i])
                {
                    max=nums[j];
                    break;
                }
            }
            res[i]=max;
        }
          
        return res;
    }
};