AcWing 830. 单调栈    原题链接    简单

作者： 作者的头像   皓首不倦 ,  2020-08-07 22:29:50 ,  所有人可见 ,  阅读 483

0 




n = int(input())
arr = list( map(int, input().split()) )


s = []
ans = []
for val in arr:
    if len(s) == 0:
        ans.append(-1)
        s.append(val)
    else:
        while len(s) > 0 and val <= s[-1]:
            s.pop(-1)
        ans.append(-1 if len(s) == 0 else s[-1])
        s.append(val)

print(' '.join(map(str, ans)))

1 评论

用户头像
迷弟   2020-09-16 20:10         踩      回复

根据你的循环逻辑，不需要特判第一个数，直接循环就好了

N = int(input())
array = list(map(int, input().split()))

s =[]
ans = []
for i in array:
    while len(s) > 0 and i <= s[-1]: #当栈顶比当前数大时
        s.pop(-1) #栈顶弹出，栈缩小
    ans.append(-1 if len(s) == 0 else s[-1]) #栈空时，（即没找到比他小的，返回-1），否则返回栈顶
    s.append(i) #把当前数放入栈中
#循环完s栈就是个单调栈 且栈顶即存在ans[]里的那个数就是第一个比当前数小的数
print(' '.join(map(str, ans)))