白駿17298大数列でロック解除

1.質問

大きさNの数列A=A 1、A 2、…、ANがあります.数列の各要素aiには、大きな数のNGE(i)が必要です.Aiの五大数は右側で、Aiより大きい数の中で一番左の数を表します.不可能な場合、5つの数は-1です.
例えば、A=[3,5,2,7]の場合、NGE(1)=5、NGE(2)=7、NGE(3)=7、NGE(4)=1となる.A=[9,5,4,8]の場合、NGE(1)=−1、NGE(2)=8、NGE(3)=8、NGE(4)=−1となる.

にゅうしゅつりょく

入力

第1行は、数列AのサイズN(1≦N≦1000000)を与える.2行目では、数列Aの要素A 1、A 2、…、AN(1≦Ai≦1000000)が与えられる.

出力
全部でN個のNGE(1)、NGE(2)、…、NGE(N)をスペースに分割して出力します.

2.問題の解釈

各インデックスの右側にインデックスより大きい値がある場合は、その値を出力します.
上記の例では、

の第1項3を基準として、右側が3より大きい項の中で最初に現れたのは5である.

の第2項5を基準として、右側が5より大きい項の中で最初に現れたのは7である.

第3項2を基準として、右側の2より大きい項のうち、最初に現れたのは7である.

第4項7を基準として右側に要素がないので-1.

3.解答

3-1)2つの重複文による解析

前の複文で、与えられた配列の各要素に従って答えを求めようとします.
サブ重複文の最初の要素の右側の要素がターゲット要素より大きい場合は、result配列に値を入れ、重複文が表示されます.ターゲット要素より大きい値が見つからない場合は、forelse文を使用して-1の値を結果配列に追加します.
最後にresult配列の要素を出力します.

n = int(input())
A = list(map(int, input().split()))
result = []
for i in range(0, n):
  for j in range(i+1,n):
    if A[j]>A[i]:
      result.append(A[j])
      break
  else:
    result.append(-1)

for ele in result:
  print(ele, end=" ")

この解の時間的複雑度はO(N^2),Nの大きさは10^6,最大演算は10^12である.Pythonの毎秒演算回数は毎秒10^8~10^9であるため,この方法はタイムアウトしない.

3-2)スタック

この解釈.
1.stackには現在の要素が含まれており、隣接する2つの要素間でのみ比較されます.
2.隣接する2つの要素のうち、右が大きいときにスタックをポップアップして答えを更新します.
3.スタックの一番上の値が現在の右側の値より小さいかどうかを確認し、小さい場合はポップアップします.
ステップ3では、スタックが空または左側の値が大きくなるまでスタックを繰り返します.

n = int(input())
A = list(map(int, input().split()))
answer = [-1] * n
stack = []

stack.append(0)
for i in range(1, n):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)

print(*answer)

このプールの時間的複雑度もO(N^2)であるが,処理された要素は比較されないため,演算回数は上のプールよりも少ない.