题解 | 下一个更大的数(二)

#include <vector>
class Solution {
public:
  //使用单调栈，找到离自己最近的比他大的值，单调递减栈，保留局部最大值，
  //因为可以循环，若按照不能循环的情况，栈中最开始没有元素，所以先让开始的时候就有前面的单调递减值
    vector<int> nextBigger(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        stack<int> stk;

        for(int i=n-2; i >= 0; --i){   //初始化
            while(!stk.empty() && nums[i] >= stk.top())stk.pop();
            stk.push(nums[i]);
        }

        for(int i=n-1; i>=0; --i){
            while( !stk.empty() && nums[i] >= stk.top()){
                stk.pop();
            }
            res[i] = stk.empty()? -1:stk.top();
            stk.push(nums[i]);
        }

        return res;
    }
};