Монотонный стек: мощный инструмент для оптимизации алгоритмов

В программировании при решении задач на массивы и последовательности часто возникает необходимость находить предыдущий или следующий элемент, удовлетворяющий определённому условию — например, ближайший больший или меньший элемент. Решать такие задачи в лоб — медленно и неэффективно. Но существует шаблон, позволяющий обрабатывать подобные задачи за линейное время — монотонный стек (monotonic stack).

В этой статье мы подробно разберём, что это такое, в каких задачах применяется, как реализуется и чем полезен.

Что такое монотонный стек?

Монотонный стек — это структура данных (обычный стек), в котором элементы поддерживают монотонность:

• Монотонно возрастающий стек — элементы в стеке идут в неубывающем порядке (от меньшего к большему).
• Монотонно убывающий стек — элементы в стеке идут в невозрастающем порядке (от большего к меньшему).

Когда мы обрабатываем массив, мы поддерживаем в стеке такую упорядоченность, удаляя из него элементы, нарушающие условие. Это позволяет находить ближайшие большие/меньшие элементы за O(n) времени, без вложенных циклов.

Простыми словами

Монотонный стек — это специальный способ использовать обычный стек (последовательную структуру данных) так, чтобы в нём элементы всегда шли в порядке возрастания или убывания. То есть, каждый новый элемент, который добавляется, сравнивается с предыдущими, и если порядок нарушается — старые элементы удаляются.

Проще говоря:

• Это обычный стек, в который мы кладём элементы только в определённом порядке.
• Например, если стек возрастающий, то каждый следующий элемент должен быть больше предыдущего — иначе предыдущие удаляются.

Представь, что ты складываешь книги в стопку так, чтобы они шли от тонкой к толстой (монотонный стек по возрастанию толщины). Если ты берёшь новую книгу, и она тоньше верхней, ты убираешь книги со стопки, пока не найдёшь, куда её положить, чтобы сохранить порядок.

Где применяется монотонный стек?

Вот лишь некоторые популярные задачи, которые можно решить с его помощью:

• Найти ближайший больший (или меньший) элемент справа/слева
• Задача про трапециевидную гистограмму — наибольший прямоугольник в гистограмме
• Задачи на температуру, акции, высоты, ценники и другие подобные структуры
• Очистка дубликатов по условию
• Нахождение длины самого длинного подмассива по условию

Принцип работы

Предположим, нам нужно для каждого элемента массива найти ближайший меньший элемент слева. Алгоритм будет следующий:

1. Заводим пустой стек.
2. Проходим по массиву слева направо.
3. Для каждого элемента:
   • Пока стек не пуст и верхний элемент больше или равен текущему, выталкиваем элементы из стека.
   • Если стек не пуст — верхний элемент стека и есть ближайший меньший слева.
   • Кладём текущий элемент в стек.

Этот подход легко адаптируется для любых условий: ближайший больший, справа или слева и т.д.

Пример использования монотонного стека

Вот пример реализации монотонного стека на Swift — задача: найти ближайший меньший элемент слева для каждого элемента массива.

func nearestSmallerToLeft(_ arr: [Int]) -> [Int] {
    var result: [Int] = []
    var stack: [Int] = []
    
    for num in arr {
        while let last = stack.last, last >= num {
            stack.removeLast()
        }
        if let last = stack.last {
            result.append(last)
        } else {
            result.append(-1)
        }
        stack.append(num)
    }
    
    return result
}

// Пример использования:
let input = [4, 5, 2, 10, 8]
let output = nearestSmallerToLeft(input)
print(output)  // [ -1, 4, -1, 2, 2 ]

Что здесь происходит:

• stack хранит кандидатов на «меньший слева»
• пока вершина стека не меньше текущего элемента — убираем её
• если стек не пуст — вершина и есть ответ
• после обработки добавляем текущий элемент в стек.

Временная сложность

Каждый элемент один раз добавляется в стек и один раз удаляется из него. Все операции — простые проверки и действия над вершиной стека. Таким образом, весь алгоритм работает за линейное время O(n).

Практические советы

• Часто удобно сохранять в стеке индексы, а не значения. Это даёт больше гибкости.
• Иногда нужно два прохода: слева направо и справа налево.
• Для двухстороннего поиска (ближайший меньший слева и справа) можно использовать два отдельных прохода и два массива.
• Помните: монотонный стек — не универсальная структура, он работает только там, где важен порядок и сравнение соседних элементов.

Заключение

Шаблон монотонного стека — мощный инструмент для решения задач на массивы, особенно когда нужно находить ближайшие большие/малые элементы. Он упрощает код и резко увеличивает производительность, превращая наивные O(n²)-решения в эффективные O(n).

Если вы участвуете в соревнованиях по программированию или просто хотите писать более быстрые и умные алгоритмы — обязательно выучите этот шаблон и попрактикуйтесь в его применении.