28203:【模板】单调栈

monotonous-stack, http://cs101.openjudge.cn/practice/28203/

给出项数为 n 的整数数列 a1...an。

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标，。若不存在，则 f(i)=0。

试求出 f(1...n)。

输入

第一行一个正整数 n。 第二行 n 个正整数 a1...an​。

输出

一行 n 个整数表示 f(1), f(2), ..., f(n) 的值。

样例输入

5
1 4 2 3 5

样例输出

2 5 4 5 0

提示

【数据规模与约定】

对于 30% 的数据，n <= 100；

对于 60% 的数据，n <= 5 * 10^3 ；

对于 100% 的数据，1 <= n <= 3 * 10^6，1 <= ai <= 10^9。

来源

P5788 【模板】单调栈，https://www.luogu.com.cn/problem/P5788

n = int(input())
a = list(map(int, input().split()))
stack = []

#f = [0]*n
for i in range(n):
    while stack and a[stack[-1]] < a[i]:
        #f[stack.pop()] = i + 1
        a[stack.pop()] = i + 1


    stack.append(i)

while stack:
    a[stack[-1]] = 0
    stack.pop()

print(*a)

n = int(input())
ans = [0 for _ in range(n)]
l = list(map(int, input().split()))
stack = []
i = 0
while i < n:
    while stack and l[i] > l[stack[-1]]:
        ans[stack.pop()] = i + 1
    stack.append(i)
    i += 1
print(*ans)