题解 | #单调栈#

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums intvector
* @return intvector<vector<>>
*/
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
// write code here
//单调栈，按照递增或递减的形式在栈中存储
stack<int> stk;
int len=nums.size();
vector<vector<int>> ans(len,vector<int>(2));</int></int></int></int></int>

    for(int j=0;j<len;j++)
    {
        int temp=nums[j];
        if(stk.empty())
        {
            ans[j][0]=-1;
            stk.push(j);
        }
        else
        {
            while(!stk.empty()&&nums[stk.top()]>=temp)
            {
                stk.pop();
            }
            //如果栈已经清空表明此时左端不存在小于x的值
            if(stk.empty())
            {
                ans[j][0]=-1;
            }
            //否则当前栈顶就是小于x的左端的小标
            else
            {
                ans[j][0]=stk.top();
            }
            stk.push(j);
        }
    }
    stack<int> stkr;
    for(int j=len-1;j>=0;j--)
    {
        int temp=nums[j];
        if(stkr.empty())
        {
            ans[j][1]=-1;
            stkr.push(j);
        }
        else
        {
            while(!stkr.empty()&&nums[stkr.top()]>=temp)
            {
                stkr.pop();
            }
            //如果栈已经清空表明此时左端不存在小于x的值
            if(stkr.empty())
            {
                ans[j][1]=-1;
            }
            //否则当前栈顶就是小于x的左端的小标
            else
            {
                ans[j][1]=stkr.top();
            }
            stkr.push(j);
        }
    }

    return ans;
}

};