Монотонный стек
Вопрос
Что такое монотонный стек и для чего он?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
Ответ
Стек, в котором значения (обычно по индексам) упорядочены по возрастанию или убыванию. Перед вставкой снимаем элементы, нарушающие порядок, и для них в этот момент находится ответ. Решает «ближайший больший или меньший слева или справа» за O(n).
Разбор
Стек, в котором значения (обычно по индексам) упорядочены по возрастанию или убыванию. Перед вставкой снимаем элементы, нарушающие порядок, и для них в этот момент находится ответ. Решает «ближайший больший или меньший слева или справа» за O(n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.