白駿-2493塔

質問する😁

左側にレーザーを発射するタワーが自分より大きいタワーでしかレーザーを発射できません.入力タワーの長さで受信タワーの番号を出力
問題そのものは難しくない.

に道を教える🤣

第1の方法

この問題はスタック問題であり,当然O(n 2)でタイムアウトエラーが発生する.
(フルナビゲーション)

第2の方法

スタックを利用する.
でも今は不完全だ

import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

result = []
stackArr = []

for i in range(len(arr)):
  if i == 0:
    stackArr.append([i, arr[i]])
  else:
    for j in range(len(stackArr)-1, -1, -1):
      if arr[i] > stackArr[j][1]:
        stackArr.pop()
    stackArr.append([i, arr[i]])

  if len(stackArr) == 1:
    result.append(0)
  else:
    result.append(stackArr[-2][0] + 1)

for i in range(len(result)):
  print(result[i], end=' ')

スタックを利用してできるだけ時間を減らそうとします.
うまくやったと思っていたのですが、69~65の間でタイムアウトできなかったので悩んでしまいました.

△大間違い…次も間違い、タイムアウトの天地です.
この方法はスタックを使ってよくできていますが、スタックの要素が多くなるとスタックがループし続けるので、あまりよくありません.
試験に落ちる

最後の方法

import sys

n = int(input())
arr = list(map(int, input().split()))

result = []
stackArr = []


for i in range(len(arr)):
  while stackArr:
    if arr[i] < stackArr[-1][1]:
      result.append(stackArr[-1][0] + 1)
      break;
    stackArr.pop()

  if not stackArr:
    result.append(0)
      
  stackArr.append([i, arr[i]])



for i in range(len(result)):
  print(result[i], end=' ')

スタックの使用は第2の方法と同じであるが、最大の違いはbreakを使用するかどうかである.2つ目は、スタックの中に最後のスタックよりずっと小さいやつが入ってきたら、例えば100000、999999、99999998......1に進むと、1に入るとスタックに積み上げられ、for loopで繰り返し文ごとにループし、resultに値を入力します.
第3の方法はそうではありません.私たちの目的は結果で、結果に値を加えると中断し、不要な重複を減らすことです.(2番目にforを使うときもbreakを使いたいのですが、デザインが違うので難しいです…)

に感銘を与える😀

スタックを長期的に考えるメリットは良いです.

一つの方法がダメなら何とかしよう