题解 | #单调栈#

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, staMin;
        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[staBig.top()][0] = i;
                vecRight[staRight.top()] = i;
                staRight.pop();
            }
            staRight.push(i);            
        }
        /*
            左面的第一个最小值的index 与 将数组翻转或，右面的第一个小值index的关系为
            index1 + index2 = len - 1;            
        */
        // step1 翻转数组
        reverse(nums.begin(), nums.end());
        // step2: 单调栈
        for (int i = 0; i < len; i++) {
            while(!staMin.empty() && nums[i] < nums[staMin.top()]) {
                vecLeft[staMin.top()] = i;
                staMin.pop();
            }
            staMin.push(i);            
        }
        // 再次翻转结果数组
        reverse(vecLeft.begin(), vecLeft.end());
        // 通过翻转后的数组的index得到之前数组的左面第一个最小值的index
        // 重新计算
        for (int i = 0; i < len; i++) {
            if(vecLeft[i] != -1) {
                vecLeft[i] = (len - 1 - vecLeft[i]);
            }
        }
     
        // 合并结果
        for(int i = 0; i  < len; i++) {
            ret[i][0] = vecLeft[i];
            ret[i][1] = vecRight[i];
            
        }
        return ret;
    }
};