单调栈

[编程题]单调栈

热度指数：7375 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 $n$ 的可能含有重复值的数组 $nums$ ，找到每一个位置 $i$ 左边最近的位置 $l$ 和右边最近的位置 $r$ ， $nums_l$ 和 $nums_r$ 比 $nums_i$ 小。

请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 $l$ 和 $r$ 。如果不存在，则值为 -1，下标从 0 开始。

数据范围： $1 \le n \le 10^5$ ， $-10^9 \le nums_i \le 10^9$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[3,4,1,5,6,2,7]

输出

[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]

示例2

输入

[1,1,1,1]

输出

[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]

算法知识视频讲解

Python3

liangzhengjie

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def foundMonotoneStack(self , nums: List[int]) -> List[List[int]]:
        # write code here
        min_left = [-1 for i in range(len(nums))]
        min_left_position = [-1 for i in range(len(nums))]
        stack = [0]

        for i in range(len(nums)):
            if nums[stack[-1]] >= nums[i]:
                while len(stack) != 0:
                    if nums[stack[-1]] >= nums[i]:
                        stack.pop()
                        continue
                    else:
                        break
            
            if len(stack) != 0:
                if nums[stack[-1]] < nums[i]:
                    min_left[i] = stack[-1]

            stack.append(i)

        min_right = [-1 for i in range(len(nums))]
        stack = [len(nums)-1]
        for i in range(len(nums)-1 - 1, -1, -1):
            if nums[stack[-1]] >= nums[i]:
                while len(stack) != 0:
                    if nums[stack[-1]] >= nums[i]:
                        stack.pop()
                        continue
                    else:
                        break
            
            if len(stack) != 0:
                if nums[stack[-1]] < nums[i]:
                    min_right[i] = stack[-1]

            stack.append(i)

        res = []
        for i in range(len(nums)):
            res.append([min_left[i], min_right[i]])
        return res

发表于 2024-05-15 22:27:32 回复(0)

Python3

success_贤

双指针感觉也可以

class Solution:
    def foundMonotoneStack(self, nums: List[int]) -> List[List[int]]:
        # write code here

        res = []
        for i in range(len(nums)):
            l, r = i, i
            while l >= 0:
                if nums[i] <= nums[l]:
                    l -= 1
                else:
                    break

            while r < len(nums):
                if nums[i] <= nums[r]:
                    r += 1
                else:
                    break
            if r == len(nums):
                r = -1
            res.append([l, r])
        return res

编辑于 2024-03-15 23:27:36 回复(0)

Python3

乐可可nice

class Solution:
    def foundMonotoneStack(self , nums ):
        # write code here
        n = len(nums)
        res = [[-1, -1] for _ in range(n)]
        stack = []
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:  # 保证stack里始终从下往上递增的
                stack.pop()
            if not stack:
                res[i][0] = -1
            else:
                res[i][0] = stack[-1]  # 这里stack的最上面比nums[i]小
            stack.append(i)  # 这里append的值肯定比pop的值要小，所以pop出来的值就没有用了
        stack.clear()
        for j in range(n - 1, -1, -1):  # 倒序
            while stack and nums[stack[-1]] >= nums[j]:  # 这里也是一样的逻辑，stack从下往上递增
                stack.pop()
            if not stack:
                res[j][1] = -1
            else:
                res[j][1] = stack[-1]
            stack.append(j)
        return res

发表于 2021-09-20 16:54:35 回复(0)