Premium

Стек

Min Стек

Реализовать стек с получением минимума за O(1)

Средний

Постановка задачи

Описание (LeetCode - 155. Min Stack)

Нужно реализовать стек, который поддерживает операции:

  1. push(val) - добавить число val в стек.
  2. pop() - удалить верхний элемент.
  3. top() - вернуть верхний элемент.
  4. getMin() - вернуть минимальный элемент в стеке.

Все операции должны работать за O(1).

Пример:

MinStack minStack = new MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.getMin()
minStack.pop()
minStack.top()
minStack.getMin()

Результат:

-3
0
-2

Ограничения:

  • -2³¹ <= val <= 2³¹ - 1
  • Операции pop, top и getMin вызываются только для непустого стека.
  • Будет выполнено не более 3 * 10⁴ операций.

Решение

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

Значит, минимум нужно поддерживать заранее.

Идея решения:

Будем хранить в стеке не одно число, а пару:

значение, минимум на момент добавления этого значения

Когда добавляем новое число val, текущий минимум после добавления равен:

min(val, предыдущий минимум)

Эту пару кладем в стек. Тогда getMin() просто смотрит на минимум в верхней паре.

Рассмотрим пример:

  1. push(-2): кладем пару (val, min).
push(-2)
  1. push(0): минимум после добавления равен min(0, -2) = -2.
push(0)
  1. push(-3): минимум становится -3.
push(-3)
  1. getMin() смотрит на минимум в верхней паре.
getMin()
  1. После pop() верхняя пара снова описывает актуальное состояние стека: top() = 0, getMin() = -2.
pop()

Мы не пересчитываем минимум после удаления. Он уже сохранен в следующей паре ниже, потому что эта пара описывает состояние стека до последнего push.

Оценка сложности

Временная сложность

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

Пространственная сложность

Для каждого элемента мы храним пару значений, поэтому пространственная сложность равна O(n).

Код решения

Приведем код решения.

type Entry struct {
    val int
    min int
}
 
type MinStack struct {
    stack []Entry
}
 
func Constructor() MinStack {
    return MinStack{
        stack: []Entry{},
    }
}
 
func (s *MinStack) Push(val int) {
    currentMin := val
    if len(s.stack) > 0 && s.stack[len(s.stack)-1].min < currentMin {
        currentMin = s.stack[len(s.stack)-1].min
    }
 
    s.stack = append(s.stack, Entry{val: val, min: currentMin})
}
 
func (s *MinStack) Pop() {
    s.stack = s.stack[:len(s.stack)-1]
}
 
func (s *MinStack) Top() int {
    return s.stack[len(s.stack)-1].val
}
 
func (s *MinStack) GetMin() int {
    return s.stack[len(s.stack)-1].min
}

Итоги

Задача Min Stack показывает, что стек может хранить не только сами элементы, но и состояние структуры данных после каждого добавления.

  1. Суть алгоритма: вместе с каждым значением мы сохраняем текущий минимум. Верхняя пара всегда описывает актуальное состояние стека.
  2. Эффективность:
    • Временная сложность: O(1) для push, pop, top и getMin.
    • Пространственная сложность: O(n), так как для каждого элемента мы храним дополнительный минимум.
  3. Граничные случаи:
    • Повторяющиеся минимумы: каждая пара хранит свой минимум, поэтому удаление одного значения не ломает ответ.
    • Один элемент: его значение одновременно является вершиной и минимумом.
  4. Оптимальное решение: мы заранее сохраняем минимум для каждого состояния стека. Поэтому после pop не нужно искать новый минимум проходом по всем элементам.
Войдите чтобы отмечать прогресс