题解 | #单调栈#

单调栈

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

单调栈

问题描述：给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括：两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。

示例

输入：[3,4,1,5,6,2,7]

返回值：[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]

方法一

思路分析

首先介绍什么是单调栈，就是在栈的先进后出基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增或者递减。对于单调递增栈，若当前进栈元素为 $e$，从栈顶开始遍历元素，把小于 $e $或者等于 $e$ 的元素弹出栈，直到遇到一个大于$ e$ 的元素或者栈为空为止，然后再把$ e$ 压入栈中。对于本题来说要想找到每一个 $i $位置左边离$ i $位置最近且值比 $arr[i] $小的位置，需要构造单调递增栈，步骤如下：

设置一个栈$stk$，设置二维数组$array$，其中$array[i][0]$表示左边位置离$ i$ 位置最近且值比 $arr[i] $小的位置，$array[i][1]$表示右边位置离$i$位置最近
从开始元素出发，从左往右，如果栈不为空，且该元素大于栈顶元素，则$array[i][0]$为栈顶元素位置，而后直接将其压入栈中；
如果该元素小于栈顶元素，则将栈顶元素移除，继续比较，直到找到栈顶元素小于该元素的情况，此时如果栈为空，则该元素的$array[i][0]=-1$，否则$array[i][0]$为栈顶元素位置，最后该元素压入栈中

对于本题来说要想找到每一个$ i$位置右边离$ i $位置最近且值比 $arr[i] $小的位置，需要构造单调递增栈，步骤如下：

设置一个栈$stk$，$array[i][1]$表示右边位置离$i$位置最近最近且值比 $arr[i] $小的位置
从最后的元素出发，从右往左，如果栈不为空，且该元素大于栈顶元素，则$array[i][1]$为栈顶元素位置，而后直接将其压入栈中；
如果该元素小于栈顶元素，则将栈顶元素移除，继续比较，直到找到栈顶元素小于该元素的情况，此时如果栈为空，则该元素的$array[i][1]=-1$，否则$array[i][1]$为栈顶元素位置，最后该元素压入栈中

图解

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int top = -1;
        int n=nums.size();
        stack<int> stk;
        vector<vector<int>> array(n);//定义一个5*2的数组存放结果
        for (int i = 0; i < array.size(); i++)
              array[i].resize(2);
        for ( int i = 0; i < n; i++ ) 
        {
        while ( !stk.empty() && nums[stk.top()] >= nums[i] ) stk.pop();//保证栈顶元素是小于待入栈的
        if ( stk.empty() ) array[i][0] = -1;//栈为空，说明该位置元素左侧没有比它小的数
        else array[i][0] = stk.top();//如果栈不为空,则左侧比其值小的元素位置距离最近
        stk.push(i);//该元素入栈
        }
        while(!stk.empty()) stk.pop();//清空栈
        for ( int i = n - 1; i >= 0; i-- ) 
        {
        while (!stk.empty() && nums[stk.top()] >= nums[i] ) stk.pop();
        if ( stk.empty() ) array[i][1] = -1;//栈为空，说明该位置元素右侧没有比它小的数
        else array[i][1] = stk.top();//如果栈不为空,则右侧比其值小的元素位置距离最近
        stk.push(i);//该元素入栈
        }
        return array;
    }
};

复杂度分析

时间复杂度：两次循环，每次循环的复杂度为$O(n)$，循环内部存在入栈出栈的操作，要想找到每一个 i 位置左边离 $i $位置最近且值比$ arr[i] $小的位置，如果数组是逆序的，那么操作的次数为 $n \times 2$ ，在寻找因此总的时间复杂度为$O(n^2)$
空间复杂度:借助于一个二维数组以及一个栈，空间复杂度为$O(n)$

方法二

思路分析

如果说方法一是根据题目所想到的，那么我们可以直接想到的方法其实是暴力搜索的办法，首先从开始元素出发遍历，从右往左循环找到该元素左侧第一个小于该元素的位置，从左往右找到第一个小于该元素的位置，如果没有则记为-1。

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int n=nums.size();
        vector<vector<int>> array(n);//定义一个5*2的数组存放结果
        for (int i = 0; i < array.size(); i++)
              array[i].resize(2);
        for(int i=0;i<n;i++)
        {
            array[i][0]=-1;
            array[i][1]=-1;
            for(int j=0;j<i;j++)
            {
                if(nums[j]<nums[i])//左侧离 i 位置最近且值比 arr[i] 小的位置
                    array[i][0]=j;
            }
            for(int j=n-1;j>i;j--)
            {
                if(nums[j]<nums[i])//右侧离 i 位置最近且值比 arr[i] 小的位置
                    array[i][1]=j;
            }
        }
        return array;
    }
};