给定一个长度为 的可能含有重复值的数组 ,找到每一个位置 左边最近的位置 和右边最近的位置 , 和 比 小。
请设计算法,返回一个二维数组,表示所有位置相应的信息。位置信息包括:两个数字 和 。如果不存在,则值为 -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]]
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ func foundMonotoneStack( nums []int ) [][]int { n:=len(nums) ans:=make([][]int,n) for i,_:=range ans{ ans[i]=[]int{-1,-1} } stk1:=[]int{} stk2:=[]int{} for i,j:=0,n-1;i<n&&j>=0;i,j=i+1,j-1{ for len(stk1)>0&&nums[stk1[len(stk1)-1]]>nums[i]{ ans[stk1[len(stk1)-1]][1]=i stk1=stk1[:len(stk1)-1] } stk1=append(stk1,i) for len(stk2)>0&&nums[stk2[len(stk2)-1]]>nums[j]{ ans[stk2[len(stk2)-1]][0]=j stk2=stk2[:len(stk2)-1] } stk2=append(stk2,j) } return ans }