Объясни монотонный стек
Вопрос
Объясни, как за O(n) найти для каждого элемента ближайший больший справа.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Начинает с наивного O(n²)
Хранит в стеке индексы, а не значения
Описывает инвариант: значения на стеке убывают
Ответ для элемента находится в момент снятия со стека
Обосновывает O(n): каждый индекс push и pop по одному разу
Что могут спросить следом
- Что изменится для ближайшего меньшего слева?
- Как быть с циклическим массивом?
- Как решить задачу о наибольшем прямоугольнике в гистограмме?
Разбор
Наивно для каждого элемента идти вправо, пока не встречу больший: O(n²). Лучше идти слева направо и держать стек индексов элементов, которым ответ ещё не найден. Значения на стеке убывают от дна к вершине. Когда приходит новый элемент, снимаю со стека всех, кто меньше него: для каждого снятого он и есть ближайший больший справа. Потом кладу его индекс. Кто остался в стеке в конце, получают -1. Каждый индекс кладётся и снимается не больше одного раза, поэтому O(n) времени и O(n) памяти. Для циклического массива прохожу его дважды по индексу i % n.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.