В программировании при решении задач на массивы и последовательности часто возникает необходимость находить предыдущий или следующий элемент, удовлетворяющий определённому условию — например, ближайший больший или меньший элемент. Решать такие задачи в лоб — медленно и неэффективно. Но существует шаблон, позволяющий обрабатывать подобные задачи за линейное время — монотонный стек (monotonic stack).
В этой статье мы подробно разберём, что это такое, в каких задачах применяется, как реализуется и чем полезен.
Что такое монотонный стек?
Монотонный стек — это структура данных (обычный стек), в котором элементы поддерживают монотонность:
- Монотонно возрастающий стек — элементы в стеке идут в неубывающем порядке (от меньшего к большему).
- Монотонно убывающий стек — элементы в стеке идут в невозрастающем порядке (от большего к меньшему).
Когда мы обрабатываем массив, мы поддерживаем в стеке такую упорядоченность, удаляя из него элементы, нарушающие условие. Это позволяет находить ближайшие большие/меньшие элементы за O(n) времени, без вложенных циклов.
Простыми словами
Монотонный стек — это специальный способ использовать обычный стек (последовательную структуру данных) так, чтобы в нём элементы всегда шли в порядке возрастания или убывания. То есть, каждый новый элемент, который добавляется, сравнивается с предыдущими, и если порядок нарушается — старые элементы удаляются.
Проще говоря:
- Это обычный стек, в который мы кладём элементы только в определённом порядке.
- Например, если стек возрастающий, то каждый следующий элемент должен быть больше предыдущего — иначе предыдущие удаляются.
Представь, что ты складываешь книги в стопку так, чтобы они шли от тонкой к толстой (монотонный стек по возрастанию толщины). Если ты берёшь новую книгу, и она тоньше верхней, ты убираешь книги со стопки, пока не найдёшь, куда её положить, чтобы сохранить порядок.
Где применяется монотонный стек?
Вот лишь некоторые популярные задачи, которые можно решить с его помощью:
- Найти ближайший больший (или меньший) элемент справа/слева
- Задача про трапециевидную гистограмму — наибольший прямоугольник в гистограмме
- Задачи на температуру, акции, высоты, ценники и другие подобные структуры
- Очистка дубликатов по условию
- Нахождение длины самого длинного подмассива по условию
Принцип работы
Предположим, нам нужно для каждого элемента массива найти ближайший меньший элемент слева. Алгоритм будет следующий:
- Заводим пустой стек.
- Проходим по массиву слева направо.
- Для каждого элемента:
- Пока стек не пуст и верхний элемент больше или равен текущему, выталкиваем элементы из стека.
- Если стек не пуст — верхний элемент стека и есть ближайший меньший слева.
- Кладём текущий элемент в стек.
Этот подход легко адаптируется для любых условий: ближайший больший, справа или слева и т.д.
Пример использования монотонного стека
Вот пример реализации монотонного стека на 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).
Если вы участвуете в соревнованиях по программированию или просто хотите писать более быстрые и умные алгоритмы — обязательно выучите этот шаблон и попрактикуйтесь в его применении.