[PS]Baek Jun#2943 TOP/PiSun
4089 ワード
アルゴリズムの問題を解く
初期プールメソッド(タイムアウト)
popを続行すると、より長い要素を探して、小さなスタックの要素を元のリストに再接続します.
改善された解法
ソースコード
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)
スタックデータ構造を使用する理由
問題では、レーザ光は左側にのみ放出されます.つまり一つの方向しかありません.
このノードを基準として,左側のノードの中で最も近い大きなノードが正解となる.スタックの場合、最新ノード(=最も近いノード)は最上位ノードにあります.また,スタックは順序を保つ.
に感銘を与える
Reference
この問題について([PS]Baek Jun#2943 TOP/PiSun), 我々は、より多くの情報をここで見つけました https://velog.io/@su-ram/PS-백준2943-탑-파이썬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol