Выбор ответа Middle Стек и монотонный стек обновлено
Стек с минимумом за O(1)
Вопрос
Нужен стек с push, pop и getMin за O(1). Как сделать?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Хранить с каждым элементом минимум на момент добавления. Каждый уровень стека помнит минимум «всего, что ниже и включая меня».
Варианты ответа
- Хранить одну переменную
minи обновлять её приpush - Искать минимум проходом по стеку при каждом
getMin - Хранить с каждым элементом минимум на момент добавленияправильный ответ
- Сортировать стек после каждого
push, минимум будет внизу
Разбор
Каждый уровень стека помнит минимум «всего, что ниже и включая меня». После pop минимум предыдущего уровня уже лежит на вершине. Все операции O(1).
- Одна переменная ломается после
popминимального элемента: прежний минимум неизвестен. - Проход даёт O(n) на
getMin. - Сортировка ломает порядок стека и стоит O(n log n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.