Стек - задача на питоне

Question

Вообще не понимаю, как решать данную задачу, прошу побольше объяснений к коду.

Реализуйте класс StackMaxEffective, поддерживающий операцию определения максимума среди элементов в стеке. Сложность операции должна быть O(1). Для пустого стека операция должна возвращать None. При этом push(x) и pop() также должны выполняться за константное время.

Формат ввода

В первой строке записано одно число — количество команд, оно не превосходит 100000. Далее идут команды по одной в строке. Команды могут быть следующих видов:

push(x) — добавить число x в стек;
pop() — удалить число с вершины стека;
get_max() — напечатать максимальное число в стеке;

Если стек пуст, при вызове команды get_max нужно напечатать «None», для команды pop — «error».

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

Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».

Пример 1:

Ввод:

10
pop
pop
push 4
push -5
push 7
pop
pop
get_max
pop
get_max

Вывод:

error
error
4
None

Пример 2:

Ввод:

10
get_max
push -6
pop
pop
get_max
push 2
get_max
pop
push -2
push -6

Вывод:

None
error
None
2

Python 3.7.3 | Ограничение времени - 1,5 секунды | Ограничение памяти - 64Mb

Мой код:

class StackMax:
    def __init__(self):
        self.items = []
        self.max_items = []

    def push(self, item):

        if bool(self.items) and bool(self.max_items):
            if item >= self.max_items[-1]:
                self.max_items.append(item)
            return self.items.append(item)
        self.items.append(item)
        self.max_items.append(item)

    def pop(self):
        if bool(self.items) and bool(self.max_items):
            if self.items[-1] == self.max_items[-1]:
                self.max_items.pop()
            return self.items.pop()
        return 'error'

    def get_max(self):
        if bool(self.items) and bool(self.max_items):
            return self.max_items[-1]
        return None

Answer 1

Подскажу сперва идею. Сделайте стек в котором хранятся как значения, так и максимумы. Например:

команда  стек                          результат
pop      []                            error
pop      []                            error
push 4   [(4, 4)]
push -5  [(4, 4), (-5, 4)]
push 7   [(4, 4), (-5, 4), (7, 7)]
pop      [(4, 4), (-5, 4)]
pop      [(4, 4)]
get_max  [(4, 4)]                      4
pop      []
get_max  []                            None

Как записывать и использовать максимумы догадайтесь сами.

P.S. Пристально поглядев на условия можно понять, что первое значение из пары не используется. То есть вам достаточно хранить только максимумы в стеке. Вот так:

команда  стек         результат
pop      []           error
pop      []           error
push 4   [4]
push -5  [4, 4]
push 7   [4, 4, 7]
pop      [4, 4]
pop      [4]
get_max  [4]          4
pop      []
get_max  []           None

Стек избыточен в этой конкретной реализации: он хранит и значения и максимумы. Зато у него нормальный интерфейс:

class StackMaxEffective:
    def __init__(self):
        self.stack_ = []

    def __bool__(self):
        return bool(self.stack_)

    def push(self, item):
        if self.stack_:
            new_max = max(item, self.stack_[-1][1])
        else:
            new_max = item
        self.stack_.append((item, new_max))

    def pop(self):
        return self.stack_.pop()[0]

    def get_max(self):
        return self.stack_[-1][1]


s = StackMaxEffective()
for _ in range(int(input())):
    cmd = input().split()
    if cmd[0] == 'pop':
        if s:
            s.pop()
        else:
            print('error')
    if cmd[0] == 'push':
        s.push(int(cmd[1]))
    if cmd[0] == 'get_max':
        if s:
            print(s.get_max())
        else:
            print('None')

БЛОГ НА HUSL

Стек - задача на питоне

Ответы (1 шт):