五大数

3954 ワード
データ構造 テキストリンク

白駿17298


ああ大数を得る
  • サイズNの数列A=A 1、A 2、…、ANがあります.
  • Aiの5つの数は右側で、Aiより大きい数の中で最も左の数を意味します.不可能な場合、5つの数は-1です.
  • 第1行は、数列AのサイズN(1≦N≦1000000)を与える.
    • 第
  • ,第2列Aの要素A 1,A 2,...,AN(1≦Ai≦1000000)が与えられる.

    • にゅうしゅつりょく


    入出力:435 2 757–1495 4 8–1 8–1

    方法


    :iの1番目の要素とi+1:の要素を二重for文で比較し、iの1番目の要素より大きい要素がある場合はflagを増やしてbreak文から終了します.flagが0の場合、iの1番目の要素より大きい要素はないので、-1を印刷し、0でない場合は比較した数字を印刷します.
    サイズは10万ですのでタイムアウトが予想されます運転中にエラー(名前エラー)O(N^2)

    知るところ


    スタックは,正確にはスタックのpop()を用いることで時間を短縮できる.O(N)
  • は、5つの数を求める必要がある数字(または5つの数を求めていない数字)をスタックに入れる.
  • スタックのtopと配列のi要素を比較します.i 2番目の要素が大数であればスタック内popiの1番目の要素をpopの1つの要素のインデックスに対応する結果値に設定します.

    • コード#コード#

    n = int(input())
arr = list(map(int, input().split()))
result = [-1]*len(arr)
stack = []

for i in range(len(arr)):
    while stack and stack[-1][0] < arr[i]:
        v, j = stack.pop()
        result[j] = arr[i]
    stack.append((arr[i], i))
print(*result)
    ブラウザの非同期メカニズムの初歩的な概要
    フラッタテスト:LCOVをリポジトリに使用するユニットテストバッジの生成