Всем привет! Меня зовут Александр, я разработчик алгоритмов. В этой статье хотел бы рассказать о структуре данных под названием монотонный стек (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
Заключение
Итак, мы рассмотрели структуру данных применяемую как один из паттернов в решении алгоритмических задач, и разобрали две популярные задачи с её использованием. Надеюсь, статья окажется полезной, поможет легче «узнавать» и решать подобные задачи в будущем. Если по прочтению появились вопросы, прошу задавать в комментариях. Также, буду благодарен за конструктивную обратную связь.
Спасибо за уделённое время!
