Определение минимального значения в стеке

Условие

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

class Stack:
    def __init__(self):
        self.stack = []
        self.min_val = 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):
        ...

Ответ

Нет: pop не пересчитывает min_val, а начальное значение 3 произвольно. Храните вместе с каждым элементом минимум префикса стека.

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

    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]

После добавления 3, 4, 2, 5, 1 минимум равен 1. После удаления 1 он станет 2, после удаления 5 останется 2, после удаления 2 станет 3. Все операции выполняются за O(1), память — O(n). Для пустого стека pop, top и get_min поднимают IndexError.