题解 | #单调栈#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    /*
    理解去记忆
    while(栈空或者curr > top) {
        top的下一个最大值就是curr
        push到ret中
    }
    将curr push到stack中。
    return ret
    staMax, staMin.
    一个一个的算，先算staMax
    
    */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        int len = nums.size();
        stack<int> staRight, staLeft;
        vector<int> vecRight (len, -1);
        vector<int> vecLeft (len, -1);
        vector<vector<int>> ret (len, vector<int> (2, -1));
        
        // 右面第一个比它小 
        for (int i = 0; i < len; i++) {
            while(!staRight.empty() && nums[i] < nums[staRight.top()]) {
                ret[staRight.top()][1] = i;
                staRight.pop();
            }
            staRight.push(i);            
        }
        // 左面第一个比它小
       for(int i = 0; i < len; i++) {
           while(!staLeft.empty() && nums[i] <= nums[staLeft.top()]) {
               staLeft.pop();
           }
           if (!staLeft.empty()) {
               ret[i][0] = staLeft.top();
           }
           staLeft.push(i);
       }
        return ret;
    }
};