Стек, умеющий быстро возвращать минимальный элемент

Условие

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

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

Ответ

Храните для каждого узла пару «значение, минимум до этого узла». Тогда текущий минимум лежит на вершине и обновляется вместе с push/pop. Связный стек даёт O(1) структурных операций без перераспределения массива.

Реализация через цепочку неизменяемых узлов:

class MinStack:
    def __init__(self):
        self.head = None

    def push(self, value):
        minimum = value if self.head is None else min(value, self.head[1])
        self.head = (value, minimum, self.head)

    def _require(self):
        if self.head is None:
            raise IndexError('Empty stack')

    def pop(self):
        self._require()
        value, _, self.head = self.head
        return value

    def top(self):
        self._require()
        return self.head[0]

    def get_min(self):
        self._require()
        return self.head[1]

Повторяющиеся минимумы обрабатываются естественно. Память O(n); сравнение самих значений предполагается O(1). Для Python-списка push обычно был бы лишь амортизированно O(1).