白駿17928号:呉大洙

4669 ワード
python ps stack テキストリンク

五大数


白駿17928号:呉大洙

アイデア


数列の大きさは10万です.O(Nlogn)時間の複雑さを持つアルゴリズムを設計すれば解ける.しかし,この問題はO(N)の時間的複雑さで解決できる.
  • に入力された数列を逆順に入れたスタックA、空のスタックB.
  • スタックBが空の場合、AからスタックBにジャンプする.
    • 要素が
  • スタックBにある場合、スタックAの上部にある要素とスタックBの上部にある要素とを比較する.
  • スタックAの上部にある要素がスタックBの上部にある要素より大きい場合、NGE(その要素のインデックス)がスタックAの上部にある要素に更新され、ポップアップされる.
  • のスタックBの最上位の要素の値は、スタックAの最上位の要素の値よりも大きいか、またはスタックBの要素が消えるまで繰り返される.
  • スタックAからポップアップされ、スタックBにプッシュされる.

    • コード#コード#

    import sys
input = sys.stdin.readline

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

targets = []
ans = [-1] * N

st.reverse()
idx = 0
targets.append((idx, st.pop()))

while st:
    t = st.pop()
    idx += 1

    while targets and targets[-1][1] < t:
        a, b = targets.pop()
        ans[a] = t
    
    targets.append((idx, t))

for i in ans:
    print(i, end=' ')

    おしゃべり


    問題を解くより絵を描いて説明するのがもっと難しい.
    TIL 63|繰り返し文のタイプと使い方1
    Spring JDBC練習4