Min Stack: стек с getMin за O(1), Max Stack и очередь с минимумом

Коротко

Min Stack — задача на проектирование структуры данных, а не на алгоритм. Код короткий, но интервьюера интересует другое: заметите ли вы, почему минимум можно хранить «слоями», не сломаетесь ли на дубликатах и сможете ли перенести идею на очередь. Ниже — три реализации, их подводные камни и задачи, которые строятся на той же мысли.

Условие

Нужно реализовать класс MinStack:

• push(val) — положить элемент на вершину;
• pop() — снять элемент с вершины;
• top() — вернуть вершину;
• getMin() — вернуть минимальный элемент стека.

Все операции — за $O(1)$. Гарантируется, что pop, top и getMin вызываются только на непустом стеке.

push(-2), push(0), push(-3)
getMin() → -3
pop()
top()    → 0
getMin() → -2

На LeetCode это задача 155, значения от $-2^{31}$ до $2^{31}-1$, до $3 \cdot 10^4$ вызовов. Если основы стека подзабылись, начните со статьи Стек и очередь.

Почему не работает одна переменная

Первая идея — хранить рядом со стеком переменную min и обновлять её при push. С push всё хорошо: новый минимум — это min(старый, val).

Проблема в pop. Если сняли элемент, который и был минимумом, какой минимум теперь? Переменная его не помнит. Пересчитать заново — $O(n)$, и требование $O(1)$ нарушено.

Сортированная структура рядом со стеком (куча или дерево) даст $O(\log n)$, но это тоже не то, что просят.

Ключевое наблюдение

У стека есть свойство, которого нет у произвольного массива: элементы снимаются строго в обратном порядке. Пока элемент на глубине k лежит в стеке, всё, что под ним, тоже на месте и не меняется.

Значит, минимум «стека до глубины k включительно» — фиксированное число. Его можно посчитать один раз в момент push и больше никогда не пересчитывать. После pop нужный минимум — тот, что был записан для нового верхнего элемента.

Все три реализации ниже — разные способы хранить эти «минимумы по слоям».

Решение 1: стек пар

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

class MinStack:
    def __init__(self):
        self.stack = []  # пары (значение, минимум на этой глубине)

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

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

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

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

Разбор на примере из условия:

Все операции — $O(1)$, память $O(n)$ на вторую компоненту пары. На собеседовании это решение стоит написать первым: оно короткое, без граничных случаев и его легко объяснить.

То же на JavaScript:

class MinStack {
  constructor() {
    this.stack = [] // [значение, минимум на этой глубине]
  }

  push(val) {
    const n = this.stack.length
    const currentMin = n ? Math.min(val, this.stack[n - 1][1]) : val
    this.stack.push([val, currentMin])
  }

  pop() {
    this.stack.pop()
  }

  top() {
    return this.stack[this.stack.length - 1][0]
  }

  getMin() {
    return this.stack[this.stack.length - 1][1]
  }
}

Решение 2: второй стек минимумов

В стеке пар много повторов: если первым положили 1, а потом тысячу чисел больше единицы, минимум 1 записан тысячу раз. Второй стек хранит минимум только тогда, когда он меняется.

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []  # невозрастающая последовательность минимумов

    def push(self, val):
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.mins[-1]:
            self.mins.pop()

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

    def getMin(self):
        return self.mins[-1]

Ловушка с дубликатами

Самая частая ошибка в этой задаче — написать в push строгое val < self.mins[-1]. Посмотрим, что сломается:

push(1), push(1)     stack = [1, 1]   mins = [1]     ← вторая единица не попала
pop()                stack = [1]      mins = []      ← сняли 1, она равна mins[-1]
getMin()             падение: mins пуст, хотя в стеке есть 1

С <= каждая копия минимума попадает в mins и снимается ровно один раз. Есть и альтернатива: хранить в mins пары (значение, счётчик) и увеличивать счётчик на дубликатах — так второй стек не растёт на тысяче одинаковых минимумов.

В худшем случае (убывающая последовательность) второй стек такой же длины, как основной, так что асимптотика памяти та же $O(n)$. Выигрыш — только на «удачных» данных. Это стоит честно сказать интервьюеру.

Решение 3: дельты и O(1) доппамяти

Если спросят «а можно без второго стека?», есть трюк: хранить в стеке не значение, а разницу val − min, где min — минимум до вставки.

• Разница ≥ 0: элемент не стал новым минимумом, его значение — min + diff.
• Разница < 0: элемент и есть новый минимум. Само значение равно текущему min, а прежний минимум восстанавливается как min − diff.

class MinStack:
    def __init__(self):
        self.stack = []  # разности val - min на момент push
        self.min = None

    def push(self, val):
        if not self.stack:
            self.stack.append(0)
            self.min = val
        else:
            self.stack.append(val - self.min)
            if val < self.min:
                self.min = val

    def pop(self):
        diff = self.stack.pop()
        if diff < 0:
            # минимум был обновлён этим элементом: восстанавливаем прежний
            self.min = self.min - diff
        if not self.stack:
            self.min = None

    def top(self):
        diff = self.stack[-1]
        return self.min if diff < 0 else self.min + diff

    def getMin(self):
        return self.min

Проверим на push(5), push(3), push(7):

Минус решения — переполнение. В Python целые произвольной длины, а в Java, C++ или Go разница 2^31 − 1 − (−2^31) не помещается в int. Нужен long, то есть 64 бита на элемент вместо 32, — и экономия памяти становится условной. Поэтому на собеседовании дельты — хороший ответ на follow-up, а не основное решение.

Сравнение

Все три класса я проверил на сотнях случайных последовательностей операций против наивного min(list) и на граничных значениях $\pm 2^{31}$.

Max Stack: когда нужно ещё и popMax

Задача Max Stack (LeetCode 716, доступна по подписке Premium) добавляет к стеку с максимумом операцию popMax(): удалить максимальный элемент, где бы он ни лежал. Если максимумов несколько, удаляется верхний.

peekMax делается так же, как getMin, — зеркально. А вот popMax ломает идею слоёв: удаляется элемент из середины, и все записанные выше него максимумы устаревают.

Простое решение: O(n) на popMax

Снимаем элементы в буфер до максимума, удаляем его и кладём буфер обратно через обычный push — он пересчитает максимумы.

class MaxStack:
    """push, pop, top, peekMax за O(1); popMax за O(n)."""

    def __init__(self):
        self.stack = []
        self.maxs = []

    def push(self, x):
        self.stack.append(x)
        self.maxs.append(max(x, self.maxs[-1]) if self.maxs else x)

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

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

    def peekMax(self):
        return self.maxs[-1]

    def popMax(self):
        target = self.maxs[-1]
        buffer = []
        while self.top() != target:
            buffer.append(self.pop())
        self.pop()
        while buffer:
            self.push(buffer.pop())
        return target

Быстрое решение: куча и ленивое удаление

Чтобы все операции были $O(\log n)$, держим два представления одних и тех же элементов: стек (порядок вставки) и кучу (порядок по значению). У каждого элемента уникальный id. Удаление из одной структуры помечает id как удалённый, а из другой он выбрасывается лениво — когда окажется наверху.

import heapq


class MaxStack:
    """Все операции за O(log n) амортизированно."""

    def __init__(self):
        self.stack = []  # пары (значение, id)
        self.heap = []  # пары (-значение, -id): при равных берём самый верхний
        self.removed = set()
        self.next_id = 0

    def push(self, x):
        self.stack.append((x, self.next_id))
        heapq.heappush(self.heap, (-x, -self.next_id))
        self.next_id += 1

    def _clean_stack(self):
        while self.stack[-1][1] in self.removed:
            self.removed.discard(self.stack.pop()[1])

    def _clean_heap(self):
        while -self.heap[0][1] in self.removed:
            self.removed.discard(-heapq.heappop(self.heap)[1])

    def pop(self):
        self._clean_stack()
        x, i = self.stack.pop()
        self.removed.add(i)
        return x

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

    def peekMax(self):
        self._clean_heap()
        return -self.heap[0][0]

    def popMax(self):
        self._clean_heap()
        x, neg_i = heapq.heappop(self.heap)
        self.removed.add(-neg_i)
        return -x

Отрицательный id в куче нужен, чтобы среди равных максимумов первым выходил самый поздний, то есть верхний в стеке. Каждый элемент удаляется из каждой структуры не больше одного раза, поэтому амортизированная сложность — $O(\log n)$ на операцию. Альтернатива — двусвязный список плюс сортированный словарь (TreeMap в Java), идея та же. Про ленивое удаление из кучи подробнее в статье про очередь с приоритетом.

Очередь с минимумом

Следующий логичный вопрос: а если нужна не стековая, а очередная дисциплина — push в конец, pop из начала и getMin? Слоёв больше нет: снимается самый старый элемент, а минимум зависит от всех новых.

Вариант 1: две стековые очереди с минимумом

Классический приём — очередь на двух стеках: inbox для вставки, outbox для извлечения. Когда outbox пуст, перекладываем в него весь inbox — порядок разворачивается, и самый старый элемент оказывается сверху. Если оба стека — стеки с минимумом из решения 1, то минимум очереди — меньший из двух минимумов.

class MinQueue:
    """Очередь на двух стеках, каждый хранит пары (значение, минимум)."""

    def __init__(self):
        self.inbox = []
        self.outbox = []

    @staticmethod
    def _push(stack, val):
        current_min = min(val, stack[-1][1]) if stack else val
        stack.append((val, current_min))

    def push(self, val):
        self._push(self.inbox, val)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self._push(self.outbox, self.inbox.pop()[0])
        return self.outbox.pop()[0]

    def getMin(self):
        candidates = [s[-1][1] for s in (self.inbox, self.outbox) if s]
        return min(candidates)

Каждый элемент перекладывается из inbox в outbox ровно один раз, поэтому pop работает за амортизированное $O(1)$, а push и getMin — за честное $O(1)$.

Вариант 2: монотонный дек

Второй способ — хранить рядом с очередью дек кандидатов в минимумы в неубывающем порядке. При вставке выкидываем с хвоста всех, кто больше нового элемента: пока новый элемент в очереди, они уже никогда не станут минимумом.

from collections import deque


class MinQueue:
    def __init__(self):
        self.items = deque()
        self.mins = deque()  # неубывающая последовательность кандидатов

    def push(self, val):
        self.items.append(val)
        while self.mins and self.mins[-1] > val:
            self.mins.pop()
        self.mins.append(val)

    def pop(self):
        val = self.items.popleft()
        if val == self.mins[0]:
            self.mins.popleft()
        return val

    def getMin(self):
        return self.mins[0]

Здесь та же ловушка с дубликатами, что и во втором стеке: выкидываем только строго больших (>), иначе снятие одной копии минимума потеряет другую. Это родственник монотонного стека, только с двумя концами.

Главное применение очереди с минимумом — минимум или максимум в скользящем окне (LeetCode 239, Sliding Window Maximum):

def sliding_window_min(nums, k):
    q = MinQueue()
    result = []
    for i, x in enumerate(nums):
        q.push(x)
        if i >= k:
            q.pop()
        if i >= k - 1:
            result.append(q.getMin())
    return result


print(sliding_window_min([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [-1, -3, -3, -3, 3, 3]

Окно сдвигается за амортизированное $O(1)$, весь проход — $O(n)$ вместо $O(nk)$.

Типичные ошибки

• Строгое < во втором стеке. Ломается на повторяющихся минимумах, разобрано выше. Самая частая причина Wrong Answer в этой задаче.
• Сравнение объектов по ссылке. В Java stack.peek() == minStack.peek() для Integer вне кеша $[-128, 127]$ сравнивает ссылки и возвращает false для равных чисел. Нужно equals или примитивы.
• Переполнение в дельтах. val − min для int в Java/C++ переполняется уже на $2^{31}-1$ и $-2^{31}$.
• Забыть пустой стек в push. В решении с парами для первого элемента нет «предыдущего минимума» — его надо обработать отдельно.
• Пытаться обновлять один min при pop. Пересчёт по всему стеку превращает getMin в $O(n)$ — ровно то, от чего просили уйти.
• Путать «стек минимумов» с монотонным стеком. Стек минимумов из решения 2 никогда не выталкивает элементы при push — он только добавляет новые минимумы. Монотонный стек выталкивает, и это другая техника.

Min Stack на собеседовании

Задача входит в популярные подборки вроде NeetCode 150, её удобно давать как разминку на 15–20 минут, чтобы потом перейти к follow-up. Удобный план:

1. Уточнить: что делать с pop/getMin на пустом стеке (обычно гарантируется непустой), какие диапазоны значений.
2. Объяснить, почему одной переменной мало, и сформулировать наблюдение про слои.
3. Написать стек пар — коротко и без граничных случаев.
4. Предложить второй стек как оптимизацию памяти и сразу проговорить <=.
5. Прогнать пример с дубликатами: push(1), push(1), pop(), getMin().

Частые follow-up вопросы:

• «Можно с O(1) доппамяти?» — дельты, с оговоркой про переполнение.
• «А Max Stack с popMax?» — простое $O(n)$ или куча с ленивым удалением за $O(\log n)$.
• «А очередь с минимумом?» — два стека с минимумом или монотонный дек.
• «Где это применяется?» — минимум в скользящем окне, история состояний с быстрым агрегатом (например, минимум цены за всё время с возможностью отката).

Для тренировки стековых задач в целом подойдут валидные скобки, обратная польская запись и Daily Temperatures.

Итог

Min Stack держится на одной мысли: в стеке нижние элементы не меняются, пока лежат верхние, поэтому агрегат по «префиксу снизу» можно посчитать при push и хранить рядом. Пары — самый надёжный способ, второй стек экономит память на типичных данных, дельты убирают доппамять ценой переполнения. Та же идея, перенесённая на два стека или монотонный дек, даёт очередь с минимумом и линейное решение задачи о минимуме в скользящем окне.

Перед собеседованием напишите стек пар и второй стек с нуля и проверьте оба на последовательности push(1), push(1), pop(), getMin().