题目描述
约翰有 N 头奶牛,编号为 1 到 N。
现在这 N 头奶牛按编号从小到大的顺序站成了一排,其中奶牛 i 的身高为 Hi。
现在,每头奶牛都向它的右侧望向那些编号较大的奶牛,对于奶牛 i 如果存在一头奶牛 j 满足 i<j 并且 Hi<Hj,那么我们称奶牛 i 需要仰视奶牛 j。
请你求出每头奶牛的最近仰视对象。
样例
输入样例:
6
3
2
6
1
1
2
输出样例:
3
3
0
6
6
0
算法1
(单调栈) $O(n)$
从右向左遍历,每次向栈中插入元素i时,将栈顶比a[i]小的元素都删去,得到一个栈底到栈顶递减的单调栈,且每次删完栈顶更小元素后,栈顶元素就是离即将插入的i最近的更大的元素(若删完后栈中无元素,则为0)。
若从左向右遍历,则枚举每个i时,离他最近的j还未插入,处于未知状态,倘若认为stk[tt]的最近更大值为i,那样在枚举后面的数时,删完栈顶后更新,可能将之前的stk[tt]的值更新掉,就不是最近的了,所以不可取。
Python 代码
n=int(input())
N=100005
a=[0]*N
for i in range(1,n+1):
a[i]=int(input())
stk=[0]*N
tt=-1
ans=[0]*N
for i in range(n,0,-1):
while tt>=0 and a[stk[tt]]<=a[i]:
tt-=1
if tt>=0:
ans[i]=stk[tt]
else:
ans[i]=0
tt+=1
stk[tt]=i
for i in range(1,n+1):
print(ans[i])