白駿#2493

白駿2493号:タワー

🦊 マイコード

from collections import deque as dq
import sys
n = int(sys.stdin.readline())

towers = [int(i) for i in sys.stdin.readline().split()]
ans = [0]*n 
stack = dq()

for idx in range(-1, -(n+1), -1): 
  next = towers[idx]
  
  if len(stack) == 0: 
    stack.append(next)
    continue
    
  else: 
    last = stack[-1] 
    
    if last>next:
      stack.append(next)
      continue
        
    else:
      poppedIdx = (idx+1)+n
      while len(stack)>0: 
        last = stack[-1]
        if last>next:
          break
        else:
          if ans[poppedIdx]==0: 
            ans[poppedIdx] = idx+n+1
            stack.pop()
          poppedIdx +=1
      stack.append(next)

print(*ans)

タワーリスト要素を後→前の順にスタックに追加
スタックに保持=受信不可
スタックからポップアップ=受信
要素を追加するたびにスタックのtopがチェックされます.
このとき、추가하는 요소>스택 topであれば、スタックtopをpop()とする.または、要素を直接追加して、次のインデックスに移動します.
スタックは空で、pop要素がなくなり、추가하는 요소<스택 topまでpop()を続行します.すべてのpopが終了したら、要素を追加して次のインデックスに移動します.
実際、スタックを利用する考えはすぐに思い出して、どのように答えを保存してどのように出力するかで長い間うろうろしていました...

🐹 1特：専制

タワーのリストを巡回すると{<탑 번호>:0}ディックシリーズが生成された.
まず[0]*nリストを発表し、タワー順に答えを保存すればいいと思っていました.しかしスタックの中でpopを見てみると答えが保存されるのではないでしょうか.今popの要素がtowersにどれだけインデックスがあるか分かりません.
そこで、インデックスを必要とせずに値を格納できるディックシリーズを思い浮かべました.タワーの高さが異なる条件が明確に定められているので、鍵としても問題ありません.
この方法には2つの問題がある.
私の知っている限りでは、ディックシリーズが出力時に保存された順序で出力される保証はありません.

出力では、for文を回し、すべての値を文字列に接続する必要があります.

2番目の問題でタイムアウトに失敗したのかもしれません

🐻 2 t:[0]*max(タワー高さ)アレイ

高さをインデックスとして、その場所に答えを保存します.高さnのタワーの答えをlist[n]に保存します.
「塔の高さは1以上10000000以下の整数です.」
メモリオーバーフローに失敗しました

🐭 3点:idxで連絡

スタックに新しい要素を追加する要素をnextと呼びます.
スタックに後ろから順番に追加されるので、nextとスタックのtopは隣接するタワーのみです.(スタックtopは、新しい要素を追加する前にポップアップする機会がないため)、forクエリのidx(すなわち、スタックに追加する新しい要素のインデックス+1)によって、ポップアップ要素のインデックスを得ることができる.
上記のコードではpoppedIdx = (idx+1)+nとしています.
popが複数回ある場合は、poppedIdxの更新に注意してください.poppedIdxをほぼ1増やし、nextの右側のタワーを確認します.それらのタワーがスタックにあるかどうかは、ansリストを見ればわかります.ans[popedIdx]が0であることは、タワーがスタック内にあることを示すため、pop()はans[poppedIdx]==0の場合のみである.

🐻‍❄️ 4 t:最初からスタックにインデックスを追加

タワーの高さではなくスタックにインデックスを追加することもできます.
タワーの配列は変更されず、インデックスはO(1)であるため、比較するたびにスタック内のインデックスを使用してタワーの高さをクエリーできます.