Алгоритм, реализующий стек со стандартными функциями push и pop и дополнительной функцией min за O(1)

Итак, оценка времени работы функция push, pop и min — O(1).

Экстремумы изменяются не часто. Фактически минимум может поменяться только при добавлении нового элемента.

Одно из решений — сравнивать добавляемые элементы с минимальным значением. Когда минимальное значение (minValue) удаляется из стека, приходится «перерывать» весь стек в поисках нового минимума. К сожалению, это нарушает ограничение на время выполнения О(1).

Если мы будем отслеживать минимум в каждом состоянии, то легко узнаем минимальный элемент. Можно, например, записывать для каждого узла текущий минимальный элемент, Затем, чтобы найти min, достаточно «вытолкнуть» вершину и посмотреть, какой элемент является минимальным.

Как только элемент помещается в стек, локальное значение минимума становится глобальным.

У решения один недостаток — если нужно обрабатывать огромный стек, то отслеживание минимального элемента потребует много ресурсов. Существует ли лучшее решение?

Оптимизировать код можно за счет использования дополнительного стека, который будет отслеживать минимумы.

Почему такое решение более эффективно? Предположим, что мы работаем с огромным стеком, первый вставленный элемент автоматически станет минимумом. В первом решение необходимо хранить n чисел, где n — размер стека. Во втором решении достаточно сохранить несколько фрагментов данных.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».