Определение текущего минимума в стеке

Условие

В стек последовательно помещаются элементы: 3 4 2 5 1. После этого вызываются методы: get_min(), pop(), get_min() и так далее. Нужно проанализировать предложенную реализацию и выяснить, будет ли метод get_min() возвращать корректное значение после того, как минимальный элемент будет удалён из стека.

class Stack:
    def __init__(self):
        self.stack = []
        self.min_val_initial = 3

    def push(self, num: int):
        self.stack.append(num)
        self.min_val = min(self.min_val, num)

    def pop(self):
        return self.stack.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        ...

В описании следует указать, что текущий код хранит только одно значение минимального элемента (self.min_val) и не обновляет его при удалении элементов из стека. Поэтому после выполнения pop(), если удалённый элемент был минимумом, метод get_min() будет возвращать устаревшее значение, что делает его работу некорректной.

Ответ

Код сначала упадёт с AttributeError: min_val не создан. Даже после исправления имени единственный сохранённый минимум устареет после pop.

В __init__ определён min_val_initial, но push обращается к min_val. Это отдельная ошибка, предшествующая проблеме удаления.

Надёжный вариант хранит пары (значение, минимум_до_этой_позиции):

def push(self, num):
    minimum = min(num, self.stack[-1][1]) if self.stack else num
    self.stack.append((num, minimum))

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

def top(self):
    return self.stack[-1][0]

def get_min(self):
    return self.stack[-1][1]

При self.stack=[] начальный минимум не нужен. После удаления 1 минимум станет 2, после удаления 5 останется 2. Дубликаты минимумов также корректно поддерживаются. Все операции O(1), на пустом стеке возникает IndexError.