Всем привет! Меня зовут Александр, я разработчик алгоритмов. В этой статье хотел бы рассказать о структуре данных под названием монотонный стек (monotonic stack) и разобрать несколько примеров задач в решении которых он применим.
Статья может быть интересна любителям решать алгоритмические задачи, в особенности тем кто готовится к собеседованию.
Описание структуры данных
Начнём с определения.
Монотонный стек - это стек, элементы которого расположены в отсортированном порядке.
Проще всего пояснить на примере. Рассмотрим монотонный стек с возрастающим порядком элементов. При добавлении нового элемента, он поочерёдно сравнивается с уже имеющимися элементами расположенными наверху стека и те из них которые оказались больше его по значению, удаляются. После чего, элемент добавляется как в обычном стеке. Таким образом, свойство монотонности поддерживается за счёт удаления "лишних" элементов.
Например, для массива [2, 5, 8, 3]:
Добавляемый элемент |
Состояние стека после добавления |
2 |
[2] |
5 |
[2, 5] |
8 |
[2, 5, 8] |
3 |
[2, |
Стек с убывающим порядком работает аналогичным образом, за исключением того что при добавлении новых элементов, удаляются меньшие элементы.
Чем такая структура данных может быть полезна в решении задач? У неё есть важное свойство. Несмотря на то, что при добавлении элемента он итеративно сравнивается с имеющимися, каждый элемент обрабатывается максимум 2 раза (при его добавлении и удалении). Поэтому все данные обрабатываются за линейное время.
Рассмотрим примеры задач.
Задача 1. Ежедневные значения температуры
https://leetcode.com/problems/daily-temperatures/description/
Уровень сложности: Medium
Дан массив temperatures содержащий целые числа соответствующие значениям температуры воздуха по дням. Рассчитать массив answer, такой что каждый его элемент содержал бы количество дней до следующего более тёплого дня, или 0 если такого дня нет.
Пример входных и ожидаемых выходных данных:
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer = [1, 1, 4, 2, 1, 1, 0, 0]
Попробуем решить эту задачу двумя способами - вначале "в лоб", прямым перебором вариантов через вложенный цикл, и потом попробуем написать более эффективное решение. Также, измерим время выполнения на входных массивах разного размера.
import random import time random.seed(42) temps_range = range(-40, 40) # Разброс температур по шкале Цельсия # Зафиксируем тестовые массивы разной длины для замера скорости temps_control = [73, 74, 75, 71, 69, 72, 76, 73] # Контрольный пример temps_1000 = random.choices(temps_range, k=1000) temps_100k = random.choices(temps_range, k=100000) temps_200k = random.choices(temps_range, k=200000) # Решение поиском через вложенный цикл def bruteforce(temps): ''' Daily temperatures problem, bruteforce solution ''' ret = [0]*len(temps) for i, temp in enumerate(temps): for j in range(i+1, len(temps)): if temps[j] > temp: ret[i] = j-i break return ret # Проверка на тестовых данных, с замером времени print('--- Bruteforce solution: ---') print('Control example:', bruteforce(temps_control)) for temps in [temps_1000, temps_100k, temps_200k]: start_time = time.perf_counter() bruteforce(temps) end_time = time.perf_counter() print(f'Input size: {len(temps)} Time: {end_time-start_time:.3f}s')
Запустим этот код:
--- Bruteforce solution: --- Control example: [1, 1, 4, 2, 1, 1, 0, 0] Input size: 1000 Time: 0.000s Input size: 100000 Time: 1.970s Input size: 200000 Time: 7.551s
Как видно из кода, решение работает за O(N2), и тайминги это подтверждают. Удвоение размера входного массива привело примерно к четырёхкратному росту времени выполнения.
Теперь напишем решение с использованием монотонного стека и сравним результаты.
def ms_solution(temps): ''' Daily temperatures problem, monotonic stack solution ''' # В стеке будем хранить пары значений (temperature, index) предыдущих дней # в порядке убывания температуры. При нахождении более тёплого дня, # будем удалять элементы для которых уже найдено решение stack = [] ret = [0]*len(temps) for i, temp in enumerate(temps): # Каждое входное значение температуры сравниваем со значением наверху стека # Если новое значение оказалось больше, записываем разницу индексов # в выходной массив и удаляем верхний элемент стека while stack and stack[-1][0] < temp: idx = stack[-1][1] ret[idx] = i-idx stack.pop() # Если значение температуры у верхнего элемента стека выше нового элемента, # значит "более тёплый" день для него пока не найден, оставим его в стеке # Также, добавим текущий элемент stack.append((temp, i)) return ret print() print('--- Monotonic stack solution: ---') print('Control example:', ms_solution(temps_control)) for temps in [temps_1000, temps_100k, temps_200k]: start_time = time.perf_counter() ms_solution(temps) end_time = time.perf_counter() print(f'Input size: {len(temps)} Time: {end_time-start_time:.3f}s')
Запустим это решение на тех же тестовых данных.
--- Monotonic stack solution: --- Control example: [1, 1, 4, 2, 1, 1, 0, 0] Input size: 1000 Time: 0.000s Input size: 100000 Time: 0.016s Input size: 200000 Time: 0.029s
Несмотря на наличие вложенного цикла, это решение выполняется за линейное время. Как видим, обработка массива длиной в 200 тысяч элементов ускорилась с 7.5 секунд до 30 миллисекунд!
Теперь, рассмотрим более сложную задачу.
Задача 2. Нахождение прямоугольника наибольшей площади в гистограмме
https://leetcode.com/problems/largest-rectangle-in-histogram/description/
Уровень сложности: Hard
Дан массив целых чисел heights, содержащий высоты столбцов гистограммы. Найти площадь наибольшего сплошного прямоугольника в гистограмме. Ширина всех столбцов равна единице.
Пример: heights = [2, 1, 5, 6, 2, 3]
Ответ: Площадь наибольшего прямоугольника равна 10
Данная задача достаточно известна и может попасться на собеседовании. Попробуйте решить её самостоятельно, мне она показалась очень интересной. Leetcode классифицирует её уровень как сложный, тем не менее с подсказкой что эта задача также решается за линейное время с помощью монотонного стека, справиться с ней не так уж сложно.
Моё решение
По сути, мы ищем интервал (i0, i1) - индексы самого левого и самого правого столбца гистограммы. При этом, площадь прямоугольника будет равна произведению длины интервала на минимальную высоту столбца в нём.
Очевидно, что искомый интервал может быть ограничен только краями гистограммы, либо столбцами ниже чем минимальный столбец внутри интервала. Иначе, мы бы могли просто добавить соседний столбец и получить прямоугольник большей площади.
Что если попробовать перебирать массив столбцов, сохраняя в монотонном стеке начальные индексы и минимальные высоты для каждого потенциального решения? И "финализировать" прямоугольники в случае если нам встретится столбец с меньшей высотой?
def largest_rectangle_area(heights): stack = [] # (i0, min_height) best_area = 0 # Добавим в гистограмму справа столбец с нулевой высотой. # Это нужно для того, чтобы в конце цикла очистить стек # и финализировать все оставшиеся решения где i1 == len(heights)-1 for i, height in enumerate(heights+[0]): index_new = i # Перебираем элементы стека пока не встретится столбец # с меньшей высотой чем у текущего столбца while stack: index_top, height_top = stack[-1] if height_top < height: break index_new = index_top # Считаем площадь прямоугольника и удаляем элемент best_area = max(best_area, height_top*(i-index_top)) stack.pop() # Добавляем элемент с высотой текущего столбца и индексом из последнего # удалённого элемента, либо текущим индексом если ничего не удалялось stack.append((index_new, height)) return best_area
Заключение
Итак, мы рассмотрели структуру данных применяемую как один из паттернов в решении алгоритмических задач, и разобрали две популярные задачи с её использованием. Надеюсь, статья окажется полезной, поможет легче «узнавать» и решать подобные задачи в будущем. Если по прочтению появились вопросы, прошу задавать в комментариях. Также, буду благодарен за конструктивную обратную связь.
Спасибо за уделённое время!
Комментарии (12)
wataru
15.02.2026 17:03Автор, вы когда задачи разбираете, если вы не объясняете логику (почему работает) и как до этого додуматься, никто не знающий решение и не поймет его. И на интервью сможет лишь воспроизвести по памяти и завалится на первом же вопросе. И придумать даже похожую задачу не сможет. А уже знающим решение ваша статья бесполезна.
И комментарии у вас в коде бесполезны. Они точно так же, как и статья, объясняют, что код делает, а не почему. Они его фактически повторяют. Ну видно же, что вы там считаете площадь и удаляете элемент из стека. Зачем вообще этот коммент? А почему площадь такая? Почему она считается при удалении?
В первой задаче вам надо добавить примерно такие рассуждения: вот мы хотим найти для каждого элемента массива ближайший справа больший его. Рассмотрим 2 соседних элемента (a[i] и a[i+1]). Если левый больше правого (a[i] >= a[i+1]), то правый никогда ни для какого числа левее не будет ответом. Потому что если a[i+1] > x, то и a[i] > x. Но индекс i ближе к x чем i+1, он же левее. Эту логику можно обобщить на любые два элемента a[i] >= a[j], i < j: для всех элементов левее a[i], a[j] никогда не будет ответом, потому что a[i] ближе.
Это ключевое наблюдение, на котором основана работа такого стека. Назовем элемент плохим, если он не может быть ни для кого ответом и хорошим наоборот. Так вот, в стеке хранятся как раз хорошие элементы. Вы добавляете элементы массива в рассмотрение по одному, удаляете те хорошие элементы, которые становятся плохими (из-за нового добавленного элемента). Ну и последний оставшийся в стеке будет ответом для нового числа. Потому что между ним и новым числом ничего больше нового нет (а если бы было, то оно осталось бы в стеке).
А вторая задача сводится к первой. Ключевое наблюдение - любой искомый прямоугольник ограничен по высоте каким-то конкретным столбцом, а по ширине идет влево и вправо до ближайшего столбца меньшего того "несущего". Иначе его можно увеличить по высоте или по ширине. Поэтому можно перебрать все столбцы в качестве "несущего", касающегося потолка прямоугольника, а дальше надо прямо как в первой задаче найти границы слева и справа - ближайшие слева и справа меньше текущего столбца. Это решение потребует двух стеков для ближайших меньших слева и справа (и два цикла вперед и назад). Вот, кстати, почему у вас в решении стек на возрастающие элементы, а не на убывающие, как в первой задаче - ведь тут ищутся ближайшие меньшие, а не больше, как в первой задаче.
Это решение можно дальше соптимизировать до одного стека и прохода, если понять, что ближайший справа будет тот, который вытесняет хороший элемент из стека. А ближайший слева - предыдущий в стеке. Поэтому вместо отдельно поиска двух горизонтальных границ, можно проверять ответ во время вытеснения элемента из стека.
Вот эти рассуждения объясняют ваше решение, а не "что если поддерживать монотонный стек".
axion-1 Автор
15.02.2026 17:03Спасибо за отзыв!
По поводу первой задачи, действительно можно было бы дать подробное описание алгоритма. Вот только нужно ли это когда решение состоит по сути из цикла с 5 строчками кода внутри? Мне кажется код в данном случае выразительнее и большинство людей пропустили бы текстовое описание.
Во второй задаче, ваше ключевое наблюдение верно, но оно есть и в статье - первые два абзаца под спойлером, практически дословно. В остальном, мои рассуждения немного отличались, и главные "инсайты" я также постарался объяснить.
wataru
15.02.2026 17:03от только нужно ли это когда решение состоит по сути из цикла с 5 строчками кода внутри?
Нужно, потому что вообще непонятно откуда это берется, как и почему работает.
Представьте себе задачу, где можно применив кучу высшей математики вывести формулу n/2 и выдать это в ответ. И вы там еще, наверное, написали бы в объяснении, как у вас сейчас: "А что, если разделить n на 2?". И комментарий в коде вида "делим n на 2". И ни слова о том, как составить уравнения, как их решать, как прийти к формуле n/2.
Там вообще одна строчка кода будет, но пользы от такого разбора задачи вообще не будет. Если решение конкретно этой слово-в-слово задачи еще можно будет запомнить, как такой вот забавный интересный факт, то решить почти такую же задачу, где ответ будет уже n/4, прочитавшие ваш "разбор" не смогут.
По второй задаче: первый абзац действительно полезен, но дальше нет никаких рассуждений о том, откуда там берется стек, что на самом деле это сведение к первой задаче. Почему вы вообще "финализируете" прямоугольник именно там, где это происходит. Надо его переписать.
RodionGork
Задачи забавные, хотя кажется что на собеседовании такое встретить можно только в какой-то фантасмагорической конторе. Да, припоминаю, в Biocad мне показывали задачку которая хитроумным образом сводится к перемножению с помощью БПФ или что-то в этом духе - но представляется что процент задач и соискателей такого класса очень невелик :)
В любом случае спасибо за статью. Наверное аккуратнее было бы назвать эту штуку "принципом" или "идеей" нежели "структурой данных" (т.к. данные она эффективно профукивает по большей части, она не для хранения строго говоря) - но в качестве "очертить общий подход" - это очень хорошо!
Ну и конечно использование реального стека в вашем коде не выглядит супер-эффективным - вместо этого поштучного "попанья" надо использовать обычный массив с указателем на "верхушку" и двоичным поиском находить куда вставляется очередной элемент и "переключается" указатель.
Alexandroppolus
Между БПФ и монотонным стеком - пропасть по сложности (если БПФ надо было запилить вручную). Ваш кейс действительно очень редкий, а вот поймать сабж на алгосекции вполне реально.
axion-1 Автор
Спасибо за комментарий! По поводу собеседований, изначально думал включить в обзор задачу лёгкого уровня, которая могла бы с большей вероятностью встретиться. Но в конце концов решил что задача про температуры лучше проиллюстрирует идею и не стал загромождать статью.
Насчёт эффективности, согласен. Цель была скорее максимальная лаконичность и наглядность кода.
Alexandroppolus
Навскидку (могу ошибаться) это не позволит существенно уменьшить количество сравнений. Стек будет большим после долгих монотонных отрезков массива, на таких отрезках у нас одно сравнение на итерацию. Выигрыш достигается, когда монотонность меняется в обратную сторону, причем каждая итерация скидывает со стека сразу много значений. Но таких итераций будет сравнительно мало. А если скидывается понемногу, то там нет особого бонуса от двоичного поиска. В общем, надо смотреть конкретные кейсы и проверять на практике.
wataru
Подтверждаю. Это даст O(n log n) алгоритм вместо O(n). Это только если сравнения считать. Крайний случай, когда удалятся из стека будет только один элемент. Тогда там будет Log(n) + log(n-1) + ... = O(n log n).
Использование бинпоиска тут бесполезно.
RodionGork
ну, резонно, от характера данных зависит
но кстати отсюда может получиться интересный кейс иллюстрирующий пример что бинарный поиск вовсе необязательно должен делить ровно пополам :)
wataru
Не важно какой там характер данных. При любом наборе данных удаление из стека по одному элементу будет O(1) амортизационно. Если мы смотрим на весь алгоритм, то можно считать что это удаление и есть O(1). А бинпоиск - O(log n), как бы вы там не делили. Поэтому весь алгоритм с бинпоиском всегда будет медленнее, потому что там n шагов O(log n), а прямое удаление из стека состоит из n шагов O(1).
Если же у вас какая-то сильно другая задача, где вам надо online определять ближайший больший элемент и вам хочется иметь жесткое ограничение времени на каждый шаг, вот тогда вы можете применить бинпоиск, получив в итоге более вычислительно сложный алгоритм, но зато с гарантиями задержек на каждый запрос.
wataru
Я этот стек в прод коммитил. И на литкоде полно задач с ним. Так что может на интервью и попасться запросто.