题解 | 单调栈

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) { 
    //单调栈：单增栈，新数来，把栈中大于它的所有数弹出，既是找最近小于它的数（），也是维护了栈的单增顺序。
    //栈保持最近最大，也就是栈中（旧数）比新数大的数舍去，因为永远取不到了，如果后数大于前一个数，就取前一个数，后数如果小于前一个数，就取比前一个数更小的数，永远取不到比前一个数大的数，所以相对于暴力算法，减去了这一部分的检索，且有按照大小顺序检索；
    //这种递增：截止递增：栈中递增，但不大于新加入的数
        int n = nums.size();
        vector<vector<int>> ans(n, vector<int>(2));

        stack<int> stk;
        for(int i=0; i<n; i++){
            while(!stk.empty() && nums[stk.top()] >= nums[i]){
                stk.pop();
            }
            if(stk.empty())ans[i][0] = -1;
            else{
                ans[i][0] = stk.top();
            }
            stk.push(i);
        }

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

        return ans;
    }
};