题解 | #单调栈#

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

解法一：
思路分析：首先分析题目，题目的意思是通过将一个给定的数组arr，找到每一个数组中的元素，然后将其左边与右边位置最近且小于arr[i]值的位置返回，一个元素包含两个位置信息L为左边的较小值位置，R为右边的较小值位置，当较小值存在就返回给较小值的下标，否则返回-1。
——单调栈主要分为单调递增栈和单调递减栈，通过访问下一个比它大（小）的元素，也就是通俗的来说，需要在数组中，比较前后元素的大小关系来解决问题。
——我们可以首先将数组中的元素从左到右访问，依次进行判断，如果是递增就一直进行入栈，否则的话就将这个小的元素的位置返回，然后再判断这个元素与前一个元素的值，如果还是小于就继续将该元素的位置返回，依次循环判断……，直到最后一个元素，没有下一个元素，就将小于它的R记为-1。
——然后从右往左进行判断，重复上述操作，即可返回最终的结果。
实例分析：输入：[3,4,1,5,6,2,7]

图片说明
最终输出[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]。
Python核心代码为：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int一维数组 
# @return int二维数组
#
class Solution:
    def foundMonotoneStack(self , nums ):
        # write code here
        if nums == []:#如果为空
            return 
        nlen = len(nums)#数组长度
        res = [[-1, -1] for i in range(nlen)]#设置存储对象，赋予初值-1
        stack = []#栈的初始状态
        for i in range(nlen):#从左往右循环
            while stack and nums[stack[-1]] > nums[i]:
                res[stack.pop()][1] = i#找到小的就出栈且将元素赋给res[][]
            stack.append(i)#append表示将i添加到列表后边
        stack = []#再次初始化
        for i in range(nlen - 1,-1,-1):#从右往左
            while stack and nums[stack[-1]] > nums[i]:
                res[stack.pop()][0] = i#找到小的元素就赋值给res[][]
            stack.append(i)#append表示将i添加到列表后边
        return res;

——在该算法中，首先需要从左往右进行循环，然后循环判断是否符合条件，当符合条件，就输出R的位置，不符合条件，则按照初始化-1走，其次从右往左进行循环，判断是否符合条件，当符合条件，就输出L的位置，不符合条件，还是按照-1走，所以其总的时间复杂度为 $O(N + M)$ ，M为栈内循环次数。因为定义了栈对象存储空间stack，所以其空间复杂度为 $O(N)$ 。

解法二：
思路分析：其次我们通过上述解法一分析，明白了本题的精髓就是要比较，不断的比较，所以本题也可以采用暴力法进行破解，就是首先定义一个容器res，然后初始化二维数组，和解法一相同，统一设为-1，然后用两个指针挨个循环。
实例分析：
图片说明
C++核心代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int len = nums.size();//数组的长度
        vector<vector<int>> res(len);//存储对象
        for(int i = 0;i < res.size();i++){
            res[i].resize(2);//设置每一层的大小为2
        }
        for(int i = 0;i < len;i++){//初始化，统一设置为-1
            res[i][0] = -1;
            res[i][1] = -1;
            for(int j = 0;j < i;j++){//搜索左侧的元素且左侧元素的值小于i对应的值
                if(nums[j] < nums[i]){
                    res[i][0] = j;//小于的话替换对应的下标
                }
            }
            for(int j = len - 1;j > i;j--){//搜索右侧的值且右侧的值小于i对应的值
                if(nums[j] < nums[i]){
                    res[i][1] = j;//小于的话替换对应的下标
                }
            }
        }
        return res;
    }
};

——因为在该暴力法中，需要定义两个指针i和j，不断的嵌套循环，所以其时间复杂度为 $O(N^2)$ ，同时定义了一个内存存储空间res，结果数组不计入空间复杂度，所以空间复杂度为 $O(1)$ 。