Проблема Hackerrank не работает для больших данных в пределах временных ограничений (проблема стека для печати максимального элемента)

Question

Задача хакерского ранга:

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

1 -Pu sh элемент x в стеке.

2 -Удалить элемент, находящийся на вершине стека.

3 -Печатать максимальный элемент в стеке.

Формат ввода

Первая строка ввода содержит целое число.

Каждая следующая строка содержит вышеупомянутый запрос. (Гарантируется, что каждый запрос действителен.)

Ограничения:

Формат вывода

Для каждого типа запроса напечатайте максимальный элемент в стеке на новой строке.

Пример ввода

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

Пример вывода

26 91

Мой код:

n=int(input())
class Stack:
    def __init__(self):
        self.stack1=[]
    def push(self,x):
        return self.stack1.append(x)
    def pop(self):
        self.stack1.pop()
        return
    def maximum(self):
        return max(self.stack1)
stack_object=Stack()
for _ in range(n):
    a=list(map(int,input().split()))
    if a[0]==1:
        stack_object.push(a[1])
    elif a[0]==2:
        stack_object.pop()
    else:
        print(stack_object.maximum()) 

с этим алгоритмом временной сложности O (n ^ 2) я могу пройти 16 из 27 тестов.

Может ли кто-нибудь поделиться более оптимизированным решение проблемы с временной сложностью O (n).

Заранее спасибо.

Answer 1

Существует простой алгоритм O (n).

Вместо того, чтобы помещать x наверху стека, просто pu sh max(x, current_top).

Затем верхний стека будет содержать максимальное значение из всех переданных на данный момент значений.

Answer 2

Стек подобен башне элементов. Представьте, как будет выглядеть каждое из перечисленных вами действий, если бы ему нужно было работать с кортежами, а не с числами, в форме:

(number, h)

, где h - это самый высокий элемент на этом уровне или ниже в башня. Например:

input 1 8 1 6 1 9 1 5 1 10 3 2 3 2 2 3
query  out  stack
1 8         [(8, 8)]
1 6         [(8, 8), (6, 8)]
1 9         [(8, 8), (6, 8), (9, 9)]
1 5         [(8, 8), (6, 8), (9, 9), (5, 9)]
1 10        [(8, 8), (6, 8), (9, 9), (5, 9), (10, 10)]
3      10
2           [(8, 8), (6, 8), (9, 9), (5, 9)]
3      9
2           [(8, 8), (6, 8), (9, 9)]
2           [(8, 8), (6, 8)]
3      8

Рабочий код:

n=int(input())
class Stack:
    def __init__(self):
        self.stack1=[(None, -float('inf'))]
    def push(self,x):
        return self.stack1.append((x, max(self.maximum(), x)))
    def pop(self):
        self.stack1.pop()
        return
    def maximum(self):
        return self.stack1[-1][1]
stack_object=Stack()
for _ in range(n):
    a=list(map(int,input().split()))
    if a[0]==1:
        stack_object.push(a[1])
    elif a[0]==2:
        stack_object.pop()
    else:
        print(stack_object.maximum())