题解 | #单调栈#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int n = nums.size();
        stack<int> leftStk;
        vector<int> leftMin(n, -1);
        for(int i = 0; i < n; i ++){
            while(!leftStk.empty() && nums[leftStk.top()] >= nums[i]) leftStk.pop();
            leftMin[i] = leftStk.empty() ? -1 : leftStk.top();
            leftStk.push(i);
        }
        stack<int> rightStk;
        vector<int> rightMin(n, -1);
        for(int i = n - 1; i >= 0; i --){
            while(!rightStk.empty() && nums[rightStk.top()] >= nums[i]) rightStk.pop();
            rightMin[i] = rightStk.empty() ? -1 : rightStk.top();
            rightStk.push(i);
        }
        vector<vector<int>> res(n);
        for(int i = 0; i < n; i ++){
            res[i] = {leftMin[i], rightMin[i]};
        }
        return res;
    }
};