给定一个长度为 的可能含有重复值的数组 ,找到每一个位置 左边最近的位置 和右边最近的位置 , 和 比 小。
请设计算法,返回一个二维数组,表示所有位置相应的信息。位置信息包括:两个数字 和 。如果不存在,则值为 -1,下标从 0 开始。
数据范围: ,
进阶:空间复杂度 ,时间复杂度
[3,4,1,5,6,2,7]
[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]
[1,1,1,1]
[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]
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
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