给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
第一行输入一个数字 n,表示数组 arr 的长度。
以下一行输入 n 个数字,表示数组的值
输出n行,每行两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。
7 3 4 1 5 6 2 7
-1 2 0 2 -1 -1 2 5 3 5 2 -1 5 -1
# 用list模拟单调栈 n = int(input()) arr = [int(k) for k in input().split()] left = [-1 for _ in range(n)] stk = [] # 左向右 for i in range(n): while stk and arr[stk[-1]] >= arr[i]: stk.pop() if stk: left[i] = stk[-1] stk.append(i) right = [-1 for _ in range(n)] stk = [] # 右向左 for i in range(n-1, -1, -1): while stk and arr[stk[-1]] >= arr[i]: stk.pop() if stk: right[i] = stk[-1] stk.append(i) for i in range(n): print(f"{left[i]} {right[i]}")
n = int(input()) arr = [int(x) for x in input().split(' ')] l=-1 r=-1 for i in range(n): if i==0: l=-1; for j in range(i+1,n): if arr[j]<arr[i]: r=j print(l,r) break if(r==-1): print(l,r) if i==n-1: r=-1 for j in range(n-2,-1,-1): if arr[j]<arr[i]: l=j print(l,r) break if(l==-1): print(l,r) if 0<i<n-1: for j in range(i-1,-1,-1): if arr[j]<arr[i]: l=j break else: l=-1 for j in range(i+1,n): if arr[j]<arr[i]: r=j break else: r=-1 print(l,r)
n = int(input()) arr = list(map(int,input().strip().split(' '))) L=[-1 for i in range(n)] R=[-1 for i in range(n)] min_t=[] for i in range(n): while len(min_t)>0 and arr[min_t[-1]] >= arr[i]: min_t.pop() if len(min_t) != 0: L[i]=min_t[-1] min_t.append(i) min_t=[] for i in range(n-1,-1,-1): while len(min_t)>0 and arr[min_t[-1]] >= arr[i]: min_t.pop() if len(min_t) != 0: R[i]=min_t[-1] min_t.append(i) for i in range(n): print(L[i],R[i])