[PS]Baek Jun#2943 TOP/PiSun

アルゴリズムの問題を解く

題:タワー。2

ソリューション:タイムアウト

分類:スタック

初期プールメソッド(タイムアウト)

塔長はforゲートに配列され、

が順次ポップアップする

各タワーの長さは短い要素よりも小さいスタックに配置されている

.
popを続行すると、より長い要素を探して、小さなスタックの要素を元のリストに再接続します.

より長い要素のインデックスを結果配列に格納します.

タイムアウトの原因:エレメントより小さいエレメントは、単独で保存する必要なく直接ポップアップできます.しかし,再存再続の過程があったため,タイムアウトが発生した.

改善された解法

各要素はforゲートで巡回する.最初から

スタックには、以前の要素の値が格納されています.

スタックに何もない場合、0出力

要素が

スタックに存在する場合、自身より小さい要素はポップアップされ、除去されます.大きな要素がある場合、インデックス出力は

です.

現在の要素をスタック

にプッシュする

ソースコード

N = int(input())
H = list(map(int, input().split()))
stack = []
for i in range(N):
    while stack:
        top = H[stack[-1]]
        if top > H[i]:
            break
        stack.pop()
    if stack == []:
        print(0)
    else:
        print(stack[-1]+1)
    stack.append(i)

スタックデータ構造を使用する理由

問題では、レーザ光は左側にのみ放出されます.つまり一つの方向しかありません.
このノードを基準として,左側のノードの中で最も近い大きなノードが正解となる.スタックの場合、最新ノード(=最も近いノード)は最上位ノードにあります.また,スタックは順序を保つ.

に感銘を与える

スタックを使用することで、どのような面が利用できるか分かりません.

スタック

を使用する場合

文字列、括弧のような特定の方向に並べ替えるときにスタックを使うのは知っていますが、スタックの特性をうまく利用していないようです.