Код Middle Стек и монотонный стек обновлено
Стек с минимумом
Условие
Стек с push, pop, top и getMin - все за O(1). Верни объект с этими методами.
Что проверяют тесты
минимум обновляется
top и pop
Как подойти
Параллельный стек минимумов: на каждом уровне лежит минимум всего, что ниже. Все операции O(1) ценой O(n) памяти. Оптимизация - хранить минимум только при его смене, но тогда усложняется pop.
Подсказки: 1
- Храни второй стек с минимумом на каждый момент времени.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.