[白準17298]おお大数(Python)

1.アイデア

巡視に向かう過程で、30分でスタックを利用して問題を解決する方法を考えたが、まだ考えていない.だから私は逆巡視して、問題を解決しようとしたが、成功した.
配列の最後の要素をstackに挿入し、次の要素から逆ブラウズを開始します.現在のインデックスによって指数付けされた要素は、stackに格納された最後の要素と比較される.popは、stackの最後の要素が現在のインデックスが指す配列の要素よりも大きいまで演算される.次に、その要素(stackの最後の要素)を別の変数に書き込む.残りのstackがなければ−1を記録する.その後、現在のインデックスによって指数付けされたグループの要素値がstackに挿入される.
白準例入力1を使用して説明する場合、入力された配列(arr)、[3, 5, 2, 7]、および大きな数を含む配列、およびanswerのすべての要素は、−1に初期化される.
まず、arrの最後の要素をstackに挿入する.そのためstack = [7]です.次いで、arrの最後に、第2の要素から第1の要素への逆探索が行われる.arr[2]は2であり、stackより小さい最後の要素7である.そのためanswer[2]=7です.2をstackに挿入します.arr[1]は5です.5はstackより大きい最後の要素2である.従ってstackにおいてpop.pop演算の後、stackの最後の要素は7である.7は5より大きく、answer[1]=7です.次に、stackに5を挿入する.arr[0]は3です.3 stack未満の最後の要素5.そのためanswer[0]=5です.
したがって、正解は[5,7,7,-1]です.

2.コード

import sys

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

def solve():
    if n == 1: return [-1]
    answer = [-1 for _ in range(n)]
    stack = []
    stack.append(arr[-1])
    for i in range(n-2, -1, -1):
        while stack and arr[i] >= stack[-1]: stack.pop()
        answer[i] = -1 if not stack else stack[-1]
        stack.append(arr[i])
    
    return answer

answer = solve()
for a in answer: print(a, end=' ')