单调栈

更多题解，请关注公众号【程序员学长】，面试高频top系列的题已经快更新完毕，需要版本答案的来~

问题描述

给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比 arri 小的位置。请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 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]]

分析问题

这道题最简单的解法就是暴力求解，即通过两层for循环来求解。如下所示：

class Solution:
    def foundMonotoneStack(self , nums):
        n=len(nums)
        res=[]
        #遍历一遍数组
        for i in range(0,n):
            l=-1
            r=-1
            #从左往右寻找l，寻找比nums[i]小的最近的nums[l]
            for j in range(0,i):
                if nums[j] < nums[i]:
                    l=j

            #从右往左寻找l，寻找比nums[i]小的最近的nums[r]
            for j in range(n-1,i,-1):
                if nums[j] < nums[i]:
                    r=j

            res.append([l,r])
        return res

该算法的时间复杂度是O(n^2)，空间复杂度是O(1)。

显然暴力求解的时间复杂度太高，那我们该如何优化呢？其实这道题我们可以使用单调栈来求解，首先我们来看一下单调栈的定义。

单调栈是指栈内元素是具有有单调性的栈，和普通栈相比，单调栈在入栈的时候，需要将待入栈的元素和栈顶元素进行对比，看待加入栈的元素入栈后是否会破坏栈的单调性，如果不会，直接入栈，否则一直弹出到满足条件为止。

本题中，我们维护一个存储数组下标的单调栈。然后遍历数组，执行如下操作。

我们以求每一个i左边离i最近且小于arr[i]的位置为例，来看一下算法的执行流程。首先我们从左往右遍历数组。

• 假设遍历到的元素是a[i]，栈顶元素top对应的数组中的元素是a[top]，然后我们拿a[i] 和 a[top]进行对比。
• 如果a[top] > a[i]，就说明top不是第i个元素的解，也不会是i以后任何元素的解（因为i比top距离后面的数更近，同时a[i] < a[top]），所以我们就把top弹出，直到栈为空或者栈顶元素（数组的下标）对应数组中的元素小于a[i]。
• 如果a[top] < a[i]，就说明第i个数的解就是top，因为栈内的元素都是单调递增的，所有top是离i最近的数，即top就是所求值。然后因为i可能是i右侧的候选解，所以把i加入栈中。

同理，我们从右往左遍历数组，就可以得到每一个i右边离i最近且小于arr[i]的位置。

下面我们来看一下代码的实现。

class Solution:
    def foundMonotoneStack(self , nums):
        n=len(nums)
        res=[]
        l=[0]*n
        r=[0]*n
        #单调栈
        stack=[]
        #从左往右遍历数组
        for i in range(0,n):
            #如果栈顶元素top对应的数组中的元素num[top]>nums[i]
            #则出栈，直到栈为空或者栈顶元素对应的数组中的元素比nums[i]小
            while stack and nums[stack[-1]] >=nums[i]:
                stack.pop()

            l[i]=stack[-1] if stack else -1
            #i入栈，因为i有可能成为i右边的答案
            stack.append(i)

        stack=[]
        #从右往左遍历数组
        for i in range(n-1,-1,-1):
            # 如果栈顶元素top对应的数组中的元素num[top]>nums[i]
            # 则出栈，直到栈为空或者栈顶元素对应的数组中的元素比nums[i]小
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            r[i] = stack[-1] if stack else -1
            # i入栈，因为i有可能成为i左边的答案
            stack.append(i)

        for i in range(0,len(l)):
            res.append([l[i],r[i]])

        return res

s=Solution()
print(s.foundMonotoneStack([3,4,1,5,6,2,7]))

该算法的时间复杂度是O(n)，空间复杂度是O(n)。