Где применяется
1. Задача
Обычный стек кладёт, снимает и показывает верх за O(1). Но на вопрос «какое здесь сейчас наименьшее значение?» быстрого ответа у него нет. Придётся просматривать весь стек, а это O(n) на каждый вопрос. Вопрос же возникает постоянно: самая низкая цена за торговую сессию, минимум в истории, которую можно откатывать, наименьший элемент, пока данные добавляются и убираются.
Min stack (стек с минимумом) отвечает на getMin за O(1). Идея за ним маленькая, но пригодится много где: держи готовый ответ рядом с данными и не пересчитывай его.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на проектирование, где стек должен за O(1) отвечать на дополнительный вопрос, например о наименьшем значении. Храни ответ для каждого уровня рядом со значением, и снятие вернёт прежний ответ.
Задача урока под тем же именем, со вторым стеком текущих минимумов.
Держи рядом со стеком второй массив с отложенной прибавкой для каждого уровня и передавай её на уровень ниже при каждом снятии.
Держи по стеку на каждую частоту и текущую наибольшую частоту, тогда pop берёт вершину самого верхнего стека.