Я получаю Прекращено из-за тайм-аута для конкретного теста, в котором мой цикл выполняется 100000 раз. Кто-нибудь может мне помочь в решении этой проблемы?

Question

Проблема: я получаю Завершено из-за тайм-аута для конкретного теста, в котором мой цикл выполняется 100000 раз. Кто-нибудь может мне помочь в решении этой проблемы?

ВОПРОС.У вас есть пустая последовательность, и вам будут заданы вопросы.Каждый запрос относится к одному из этих трех типов:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.
Input Format

The first line of input contains an integer N, . The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

Constraints 



Output Format

For each type 3 query, print the maximum element in the stack on a new line.

Sample Input

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3
Sample Output

26
91

//My Code

# Enter your code here. Read input from STDIN. Print output to STDOUT
stack=[]
top=-1
n=int(input())
for i in range(n):
    x=list(map(int,input().split()))
    if x[0]==1:
        top+=1
        stack.append(x[1])
    elif x[0]==2:
        top=top-1
        stack.pop()
    else:
        print(max(stack))        

Контрольный пример для прерванного тайм-аута: 100000 1 86627537 1 938778873 1 495914598 3 3 3 3 3 3 1 507065127 1 230961732 3 1 641113507 1 123729858 1 706231036 3 1218881566 1 759861012 3 {- укорочено -}

Answer 1

Поскольку вы всегда печатаете максимальное значение, возможно, имеет смысл сохранить отдельный отсортированный массив.Я могу только догадываться, что вызов max(stack) является «тайм-аутом» в этом тестовом примере, потому что он ищет несортированный список.

Полагаю, это урок алгоритмической сложности.Поддержание отсортированного массива и извлечение максимального значения имеет время поиска O(1), где вызов max() зависит от реализации.