[白俊#2493]塔

1.問題の説明

2.解説

O(n^2)の時間的複雑さで解き始めたところ,タイムアウトが発生し,時間的複雑さをどのように減らすかを考えた.

まず左からタワーをチェックし、インデックス、値のペアを組み合わせてスタックに挿入します.

idxは、1からスタックがアイドルになるまでスタックの一番上のvalがスタックの一番上のvalよりも大きい場合、結果配列にスタックの一番上の値を挿入します.そうしないとスタックはポップアップします()

while文が終了すると、現在のインデックスと値のペアがスタックに挿入されます.

説明がもっと難しいので、コードを読んでほしいです.私は本当に説明できません.

3.コード

import sys
input = sys.stdin.readline

N = int(input())
tower = list(map(int, input().split()))
stack = []
res = [0] * N

for idx, val in enumerate(tower):
    if idx == 0:
        stack.append([idx, val])
        continue
    else:
        while stack:
            if val < stack[-1][1]:
                res[idx] = stack[-1][0] + 1
                break
            else:
                stack.pop()
        stack.append([idx, val])

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