Два варианта решения #problem46@tproger про реализацию стека с push/pop/min, работающими за O(1). Читать на сайте: http://vk.cc/3IbUVI
Экстремумы изменяются не часто. Фактически минимум может поменяться только при добавлении нового элемента.
Одно из решений — сравнивать добавляемые элементы с минимальным значением. Когда минимальное значение (minValue) удаляется из стека, приходится “перерывать” весь стек в поисках нового минимума. К сожалению, это нарушает ограничение на время выполнения О(1).
Если мы будем отслеживать минимум в каждом состоянии, то легко узнаем минимальный элемент. Можно, например, записывать для каждого узла текущий минимальный элемент, Затем, чтобы найти min, достаточно “вытолкнуть” вершину и посмотреть, какой элемент является минимальным.
Как только элемент помещается в стек, локальное значение минимума становится глобальным. Код на первом рисунке.
У решения один недостаток — если нужно обрабатывать огромный стек, то отслеживание минимального элемента потребует много ресурсов. Существует ли лучшее решение?
Оптимизировать код можно за счет использования дополнительного стека, который будет отслеживать минимумы. Смотрите второй рисунок.
Почему такое решение более эффективно? Предположим, что мы работаем с огромным стеком, первый вставленный элемент автоматические станет минимумом. В первом решение необходимо хранить n чисел, где n — размер стека. Во втором решении достаточно сохранить несколько фрагментов данных.
Разбор по книге Гейл Л. Макдауэлл «Cracking the Coding Interview».
#solutions@tproger
