В каждом узле стека храните значение и минимум среди этого узла и всех элементов ниже него. При добавлении вычисляйте новый минимум, при удалении переходите к предыдущему узлу. Тогда push, pop и getMin требуют O(1) действий, а весь стек занимает O(n) памяти.
Как реализовать MinStack с получением минимума за O(1)?
Реализация MinStack на JavaScript: сохраняем минимум в каждом узле, поддерживаем повторяющиеся значения и выполняем операции за O(1).
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Реализуйте стек с методами push(value), pop() и getMin(). Добавление, удаление верхнего элемента и получение минимального значения должны выполняться за постоянное время.
Идея решения
Свяжем элементы стека в односвязный список. Каждый узел хранит своё значение, ссылку на предыдущий узел и минимум на соответствующей глубине. При удалении вершины нужный минимум уже записан в следующем узле: пересчитывать его по всему стеку не нужно.
Для определённости принимаем только конечные числа. pop() возвращает удалённое значение; pop() и getMin() у пустого стека выбрасывают RangeError.
Реализация
class MinStack {
#head = null;
push(value) {
if (!Number.isFinite(value)) {
throw new TypeError('Ожидается конечное число');
}
this.#head = {
value,
min: this.#head === null ? value : Math.min(value, this.#head.min),
next: this.#head,
};
}
pop() {
if (this.#head === null) throw new RangeError('Стек пуст');
const value = this.#head.value;
this.#head = this.#head.next;
return value;
}
getMin() {
if (this.#head === null) throw new RangeError('Стек пуст');
return this.#head.min;
}
}
Проверка
const stack = new MinStack();
stack.push(3);
stack.push(1);
stack.push(1);
console.log(stack.getMin()); // 1
console.log(stack.pop()); // 1
console.log(stack.getMin()); // 1: второй минимум остался
console.log(stack.pop()); // 1
console.log(stack.getMin()); // 3
Сложность и типичные ошибки
В обычной алгоритмической модели каждая операция выполняет фиксированное число действий: время O(1), общая память O(n). Реальные задержки выделения памяти и сборки мусора эта оценка не описывает.
Нельзя хранить только один текущий минимум: после его удаления придётся искать следующий по всему стеку. Пересчёт через Math.min(...values) тоже не даёт O(1). Вариант с двумя массивами допустим при обсуждении амортизированной сложности добавления, но связный список позволяет не опираться на перевыделение массива.
Проверьте повторяющиеся минимумы, отрицательные числа, удаление последнего элемента и повторное использование опустевшего стека.