循环数组单调栈

---

image.png image.png

• 一个点前后的点都可以是它的解，同一个点相等肯定不会入栈。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<pair<int,int>>stack;
        vector<int>res;
        for(int i=nums.size()-1;i>=0;i--){
            stack.push_back(make_pair(nums[i],i));
        }
        for(int i=nums.size()-1;i>=0;i--){
            // i [0,len-1] 
            while(!stack.empty()&&stack.back().first<=nums[i]){
                stack.pop_back();
            }
        
            // 可能出现遍历完后面倍增数组的情况
            if(stack.empty()){
                res.push_back(-1);
            }
            else{
                res.push_back(stack.back().first);
            }
            stack.push_back(make_pair(nums[i],i));
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

或者简化一下：直接暴力空的stack从后往前遍历，res取i%n，相当于先考虑一轮后序遍历，再进行一轮后序遍历，相当于第一轮是考虑后边的更大值，第二轮是解决后面没有更大值的情况下考虑前面的情况。如果前面后面都有更大值也不怕，因为第二轮遍历会用后面的最大值覆盖掉前面的最大值的解。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        stack<int> s;
        // 假装这个数组长度翻倍了
        for (int i = 2 * n - 1; i >= 0; i--) {
            // 索引要求模，其他的和模板一样
            while (!s.empty() && s.top() <= nums[i % n])
                s.pop();
            res[i % n] = s.empty() ? -1 : s.top();
            s.push(nums[i % n]);
        }
        return res;
    }
};