Информатика · объяснение и практика
Как монотонный стек находит следующий больший элемент
Для каждого элемента находим первый больший справа, ведём стек нерешённых позиций и отдельно разбираем равные значения и линейную стоимость.

В теме Структуры данных · Учебная карта
Главная мысль
Монотонный стек позволяет находить следующий строго больший элемент справа за один проход. В стеке остаются позиции, для которых ответ ещё не найден; новый элемент закрывает с вершины все меньшие значения, но не равные ему.
Стек хранит незакрытые вопросы
Возьмём массив [6,2,5,5,8]. Сначала позиции со значениями 6 и 2 ждут большего справа. Приходит 5: для 2 это первый подходящий элемент, поэтому ответом становится 5, а позиция 2 удаляется из стека. Для 6 значение 5 ещё недостаточно велико.
Следующая пятёрка равна предыдущей и не закрывает её при условии «строго больше». Когда приходит 8, она последовательно закрывает обе пятёрки и шестёрку. Сама восьмёрка остаётся без ответа: справа больше нет значений. Лучше записать отсутствие отдельной отметкой, а не числом, которое может встретиться в данных.
Пример
Следующие большие значения: [8,5,8,8,нет].
Для двух одинаковых пятёрок ответы одинаковы, но это разные позиции. Хранение индексов позволяет заполнить нужную клетку ответа и при необходимости вычислить расстояние до неё.
Почему удалённая позиция больше не понадобится
Обрабатываем элементы слева направо. Пока позиция находится в стеке, ни один уже просмотренный элемент справа от неё не подошёл. Если текущий элемент оказался больше, он действительно первый подходящий: более раннего ответа не было. Значит, эту позицию можно окончательно убрать и сохранить найденный индекс.
В стеке значения от основания к вершине идут невозрастающе. Для нового числа достаточно смотреть на вершину: после удаления меньших там останется значение не меньше текущего или стек опустеет. Проверка всех прежних элементов при каждом шаге потеряла бы главное преимущество структуры. Отдельно выпишите условие сравнения перед реализацией.
Почему вложенный цикл не делает поиск квадратичным
На одном шаге новый максимум способен удалить много позиций сразу. Но каждая позиция добавляется ровно один раз и удаляется не более одного раза. Поэтому суммарное число добавлений и удалений линейно, хотя внутри прохода присутствует цикл. Оценивается общее движение элементов, а не максимальная длина одного шага.
Для запроса «следующий больший или равный» удаление с вершины происходит уже при равенстве. Для поиска ближайшего меньшего меняют направление сравнения. Эти версии нельзя объединять одной неопределённой фразой «подходящий сосед»: одинаковые числа дают разные результаты. В учебной проверке полезны возрастающий массив, убывающий массив и несколько равных подряд — они выявляют разные ошибки границы и строгого знака.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли хранить только значения вместо индексов?
Для вывода значений иногда да, но тогда сложнее различать повторы и записывать ответ на конкретную позицию. Индексы подходят и для значения, и для расстояния.
Почему это не поиск максимума всего суффикса?
Нужен первый больший справа, а не самый большой. Например, после 3 могут идти 4 и 9: ближайший подходящий ответ равен 4.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Когда нужен стек, а когда очередь
Выбираем дисциплину извлечения для отмены действий и очереди заданий, проверяем порядок на короткой последовательности и различаем интерфейс структуры с её реализацией.
Открыть темуКак обновить сумму окна, не пересчитывая все элементы
Вычисляем суммы последовательных окон фиксированной длины, выводим обновление через уходящий и новый элементы и проверяем количество окон.
Открыть тему