题解 | 单调栈

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

        for(int i=nums.size()-1;i>=0;i--){
            while(!s.empty()&&nums[i]<nums[s.top()]){
                int index=s.top();
                rel[index][0]=i;
                s.pop();
            }
            s.push(i);
        }

        return rel;
    }
};

单调栈的模板，求一个数的左右最近的小于该数的下标位置，可知的是左右是对称的所以代码相差不大，先考虑右边，我们很容易想到暴力的n方做法，但是会超时，这是就需要单调栈进行优化，单调栈重要的单调，我们借助暴力模拟的思路，在每次遍历数组的时候，同时加上栈的这部分操作，注意栈里面存的是下标，而不是元素本身，因为单调栈的话会破坏元素本来的顺序，用下标就能完美映射出元素原本在数组中的位置，将这个数跟栈顶元素比较，如果小于栈顶代表该元素是要找的答案，那么我们就记录坐标，同时更新栈顶为该元素，为什么要更新呢，原因有两个，第一是题目要求返回每个元素的左右临近小元素的下标，而我们就是通过将每个元素的小标存入栈里才判断的，第二就是这样可以保证单调递增，后来的元素一定比前面入栈的大，这样就保证第一次小于的位置就是答案。