NC157 单调栈

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        int len=nums.size();
        //调用vector的无参构造函数创建一个长度为len，宽为1的二维容器
        vector<vector<int>> ans(len);
        //遍历二维容器的每一行，调用resize函数将容器的每一行的列宽都扩大为2
        for(int i=0;i<len;i++) ans[i].resize(2);
        //写两个单调栈
        stack<int> stack1;
        //正向遍历，如果栈非空，并且栈顶元素比要入栈的元素大，则让栈顶的元素出栈
        //判断一下，如果栈为空，则表示该元素的左边没有比本元素小的元素，输出-1
        //否则输出向左遍历找到的第一个比当前的元素小的元素（单调栈）
        //将当前的元素入栈
        for(int i=0;i<len;i++){
            while(!stack1.empty()&&nums[stack1.top()]>=nums[i]){
                stack1.pop();
            }
            if(stack1.empty()) ans[i][0]=-1;
            else  ans[i][0]=stack1.top();
            stack1.push(i);
        }
        //将刚刚构造的单调栈清空
        //逆向遍历重新构造一个单调栈，用于查找当前元素右边第一个比当前元素小的元素
        while(!stack1.empty()) stack1.pop();
        for(int i=len-1;i>=0;i--){
            while(!stack1.empty()&&nums[stack1.top()]>=nums[i]){
                stack1.pop();
            }
            if(stack1.empty()) ans[i][1]=-1;
            else ans[i][1]=stack1.top();
            stack1.push(i);
        }
        return ans;
    }
   
};