题解 | 栈和排序

import sys

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

z = []
right_max = [0] * (n+1)
res = []

#先计算后面未输入中的最大值，从后往前遍历求每个位置对应后面的最大值数组
for j in range(n-1,-1,-1):
    right_max[j] = max(s[j],right_max[j+1]) 

for i in range(n):
    if len(z)==0 :
        z.append(s[i])
    elif s[i] < right_max[i]: #遍历到的元素＜未输出的最大值，则入栈
        z.append(s[i])

    else:
        res.append(s[i]) #输出最大值，
        while z and z[-1] > right_max[i+1]: #当栈顶元素>后面的最大值时继续输出
            res.append(z.pop())

#清空栈中残留元素
while z:
    res.append(z.pop())

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