题解 | #单调栈#

单调栈

http://www.nowcoder.com/practice/ae25fb47d34144a08a0f8ff67e8e7fb5

题意：

给定一个数组（可含重复值），找到每个元素左边和右边比它小且离它最近的数组位置。

方法一：暴力解法

解题思路：

对于每个元素，都向左和向右找比它小的即可。

代码如下：

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int n=nums.size();
        vector<vector<int>> ans(n,vector<int>(2,-1));
        //遍历数组元素
        for(int i=0;i<n;i++){
            //向左寻找比当前小的
            for(int left=i-1;left>=0;left--){
                if(nums[left]<nums[i]){
                    //找到，赋值ans，并跳出
                    ans[i][0]=left;
                    break;
                }
            }
            //向右寻找比当前小的
            for(int right=i+1;right<=n-1;right++){
                if(nums[right]<nums[i]){
                    //找到，赋值ans，并跳出
                    ans[i][1]=right;
                    break;
                }
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ ，双重循环。

空间复杂度： $O (1)$ ，常数个临时变量。

方法二：单调栈

解题思路：

利用单调递增栈来存遍历过程中的元素，如果当前元素大于栈顶元素，则直接入栈，所有栈内元素目前还没有找到比它小的；如果当前元素小于栈顶元素，则循环出栈直到当前元素入栈后满足单调栈，那么对于出栈的部分元素，则当前元素就是离最近且比它小的。

图解如下：

alt

代码如下：

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        //s为单调递增栈
        stack<int> s;
        int n=nums.size();
        vector<vector<int>> ans(n,vector<int>(2,-1));
        //从左往右遍历，并将数组位置存入单调栈中
        s.push(0);
        int i=1;
        while(i<n){
            if(nums[i]>=nums[s.top()]){//递增，直接入栈
                s.push(i);
            }else{//不满足单调增，循环出栈，出栈的部分元素已经找到右边离它最近且值比它小的,
                  //给ans赋值，循环出栈完毕后再入栈
                while(!s.empty()&&nums[s.top()]>nums[i]){
                    ans[s.top()][1]=i;
                    s.pop();
                }
                s.push(i);
            }
            i++;
        }
        //清空栈中元素，初始已赋值-1
        while(!s.empty()){
            s.pop();
        }
        //从右往左遍历，并将数组位置存入单调递增栈中
        s.push(n-1);
        i=n-2;
        //该部分同上
        while(i>=0){
            if(nums[i]>=nums[s.top()]){
                s.push(i);
            }else{
                while(!s.empty()&&nums[s.top()]>nums[i]){
                    ans[s.top()][0]=i;
                    s.pop();
                }
                s.push(i);
            }
            i--;
        }
        return ans;
    }
};