Стек, умеющий быстро находить минимум

Условие

Необходимо создать структуру данных «стек», поддерживающую четыре операции:

• push(x) — добавить элемент x в стек;
• pop() — удалить элемент, находящийся на вершине стека;
• top() — вернуть текущий верхний элемент без его удаления;
• get_min() — вернуть наименьшее значение среди всех элементов стека. Все перечисленные операции должны работать за постоянное время O(1).

Ответ

Храните в каждой позиции стека пару из значения и минимума всех элементов до этой позиции. Тогда pop автоматически восстанавливает предыдущий минимум.

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

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

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

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

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

Повторяющиеся минимумы не создают проблемы: каждая позиция хранит собственный снимок минимума. top, pop, get_min на пустом стеке дают IndexError. Память O(n); push для динамического списка имеет амортизированное O(1), остальные операции — O(1). Для строгого worst-case push можно использовать связанные узлы.