Создание стека с поддержкой минимального элемента

Условие

Необходимо построить структуру данных стек, обеспечивающую три базовых операции: добавление нового элемента (push), удаление верхнего элемента (pop) и мгновенный доступ к наименьшему значению, находящемуся в стеке в данный момент.

Ответ

Храните вместе с каждым значением минимум на глубине этого элемента. Тогда Push, Pop и Min выполняются за O(1), а удаление текущего минимума автоматически восстанавливает предыдущий.

Пример Go с безопасным признаком пустоты:

type stackItem struct { value, minimum int }
type MinStack struct { items []stackItem }
func (s *MinStack) Push(value int) {
    minimum := value
    if n := len(s.items); n > 0 && s.items[n-1].minimum < minimum {
        minimum = s.items[n-1].minimum
    }
    s.items = append(s.items, stackItem{value, minimum})
}
func (s *MinStack) Pop() (int, bool) {
    n := len(s.items)
    if n == 0 { return 0, false }
    value := s.items[n-1].value
    s.items = s.items[:n-1]
    return value, true
}
func (s *MinStack) Min() (int, bool) {
    n := len(s.items)
    if n == 0 { return 0, false }
    return s.items[n-1].minimum, true
}

Push имеет амортизированную O(1) из-за роста слайса, остальные — O(1); память O(n). Повторяющиеся минимумы обрабатываются правильно. Конкурентный доступ здесь не предусмотрен.