白駿17298号オークスパイソン

1214 ワード
テキストリンク
五大数
質問する
大きさ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)を与える.第二に、数列Aの要素A 1、A 2、…AN(1≦Ai≦1000000)が与えられる.
しゅつりょく
全部でN個のNGE(1)、NGE(2)、…、NGE(N)をスペースに分割して出力します.
import sys

n = int(sys.stdin.readline())

stack = list(map(int, sys.stdin.readline().split()))
result = []
for i in range(n):
    for j in range(i+1, n):
        if stack[i] < stack[j]:
            result.append(stack[j])
            break
    else:
        result.append(-1)

for i in result:
    print(i, end=' ')
対応するコードで記述しましたが、タイムアウトで失敗しました.
import sys

n = int(sys.stdin.readline())

numbers = list(map(int, sys.stdin.readline().split()))
stack = []
result = [-1 for _ in range(n)]
for i in range(len(numbers)):
    while len(stack)!=0 and numbers[stack[-1]] < numbers[i]:
        result[stack.pop()] = numbers[i]
    stack.append(i)

for i in result:
    print(i, end=' ')
二重文はタイムアウトする必要があり、スタック資料構造を利用して解答しなければならない.
[10655]一手
チャットアプリケーションの作成-socket(4)