Минимум в стеке за O(1)

Минимум в стеке за O(1)

Это классическая задача на оптимизацию. Нужно реализовать стек, где операция getMin() работает за O(1), а не O(n).

Решение: Вспомогательный стек минимумов

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

class MinStack:
    def __init__(self):
        # Основной стек для всех элементов
        self.stack = []
        # Вспомогательный стек для минимумов
        # На вершине всегда текущий минимум
        self.min_stack = []
    
    def push(self, x: int) -> None:
        """Добавить элемент"""
        self.stack.append(x)
        
        # Если min_stack пуст или x меньше текущего минимума
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
    
    def pop(self) -> None:
        """Удалить верхний элемент"""
        if self.stack:
            # Если удаляемый элемент равен минимуму
            if self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            self.stack.pop()
    
    def top(self) -> int:
        """Получить верхний элемент"""
        return self.stack[-1] if self.stack else None
    
    def getMin(self) -> int:
        """Получить минимальный элемент за O(1)"""
        return self.min_stack[-1] if self.min_stack else None

# Пример использования
stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)

print(stack.getMin())  # -3
stack.pop()
print(stack.getMin())  # -2
print(stack.top())     # 0
stack.pop()
print(stack.getMin())  # -2

Как это работает

Шаг за шагом:

Операция: push(-2)
stack:     [-2]
min_stack: [-2]   (первый элемент)

Операция: push(0)
stack:     [-2, 0]
min_stack: [-2]   (0 > -2, не добавляем)

Операция: push(-3)
stack:     [-2, 0, -3]
min_stack: [-2, -3]  (-3 < -2, добавляем)

Операция: getMin()
Возвращаем: -3 (вершина min_stack)

Операция: pop()
Удаляем: -3
stack:     [-2, 0]
min_stack: [-2]   (-3 был минимумом, удаляем его)

Операция: getMin()
Возвращаем: -2

Сложность

• push: O(1)
• pop: O(1)
• top: O(1)
• getMin: O(1) ← Главное преимущество
• Память: O(n) в худшем случае (когда все элементы отсортированы в убыл)

Вариант 2: Более экономный по памяти

Вместо хранения самих значений, храним разницу между текущим элементом и минимумом:

class MinStackOptimized:
    def __init__(self):
        self.stack = []
        self.min_value = float('inf')
    
    def push(self, x: int) -> None:
        # Если это новый минимум
        if x <= self.min_value:
            # Сохраняем старый минимум в стек
            self.stack.append(self.min_value)
            self.min_value = x
        
        self.stack.append(x)
    
    def pop(self) -> None:
        if self.stack:
            x = self.stack.pop()
            # Если удаляем элемент, который был минимумом
            if x == self.min_value:
                self.min_value = self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1] if self.stack else None
    
    def getMin(self) -> int:
        return self.min_value

# Пример
stack = MinStackOptimized()
stack.push(-2)
stack.push(0)
stack.push(-3)
print(stack.getMin())  # -3

Минусы: сложнее для понимания, хотя экономит небольшой объём памяти.

Вариант 3: С одним стеком (компактный)

class MinStackCompact:
    def __init__(self):
        # Храним кортежи (значение, текущий минимум)
        self.stack = []
    
    def push(self, x: int) -> None:
        if not self.stack:
            # Первый элемент
            self.stack.append((x, x))
        else:
            current_min = min(x, self.stack[-1][1])
            self.stack.append((x, current_min))
    
    def pop(self) -> None:
        if self.stack:
            self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1][0] if self.stack else None
    
    def getMin(self) -> int:
        return self.stack[-1][1] if self.stack else None

# Пример
stack = MinStackCompact()
stack.push(-2)
stack.push(0)
stack.push(-3)
print(stack.getMin())  # -3

Это самое чистое и читаемое решение.

Тестовые случаи

def test_min_stack():
    stack = MinStack()
    
    # Тест 1: базовый
    stack.push(-2)
    assert stack.getMin() == -2
    stack.push(0)
    assert stack.getMin() == -2
    stack.push(-3)
    assert stack.getMin() == -3
    
    # Тест 2: pop
    stack.pop()
    assert stack.getMin() == -2
    
    # Тест 3: top
    assert stack.top() == 0
    
    # Тест 4: одинаковые минимумы
    stack2 = MinStack()
    stack2.push(-1)
    stack2.push(-1)
    stack2.push(-1)
    assert stack2.getMin() == -1
    stack2.pop()
    assert stack2.getMin() == -1
    
    # Тест 5: положительные числа
    stack3 = MinStack()
    stack3.push(5)
    stack3.push(3)
    stack3.push(7)
    assert stack3.getMin() == 3
    
    print("Все тесты пройдены!")

test_min_stack()

Вариант с использованием collections.deque (производительнее)

from collections import deque

class MinStackDeque:
    def __init__(self):
        self.stack = deque()
        self.min_stack = deque()
    
    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
    
    def pop(self) -> None:
        if self.stack:
            if self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1] if self.stack else None
    
    def getMin(self) -> int:
        return self.min_stack[-1] if self.min_stack else None

На собеседовании

Оптимальное решение — использовать два стека (основной + минимумов):

✅ Плюсы:

• O(1) для всех операций
• Легко понять и объяснить
• Надёжно и без ошибок

⚠️ Минусы:

• Требует дополнительную память O(n)

Альтернатива — компактный вариант с кортежами:

• Немного экономнее по коду
• Столь же понятен
• Однозначно лучший выбор

Эта задача часто встречается на собеседованиях в FAANG компаниях и показывает навык оптимизации алгоритмов.