Donutsプロコンチャレンジ2015 C - 行列のできるドーナツ屋

問題原文

atcoder.jp

解法

人 について考えている時、

1. いま見えている人の数を の答えとする
2. いま見えている人のうしろから見て行って、 より小さいものは今後見えなくなるので削除
3. を今見えている人として末尾に追加

で解ける。
これはスタックを使うと楽に実現できる。

本質的には、

at274.hatenablog.com

と同じにみえる。

実装

番兵を先に積んでおくと楽です。

N = int(input())
H = list(map(int, input().split()))
ans = [-1] * N

stack = [float('inf')]
for i, h in enumerate(H):
    ans[i] = len(stack) - 1
    while stack[-1] < h:
        stack.pop()
    stack.append(h)

print(*ans, sep='\n')

感想

このテクニック、いい。（特に平衡二分木が標準で備わってない言語は）