Наибольший прямоугольник в гистограмме и в матрице из единиц: монотонный стек

LeetCode 84 и 85 по шагам: от перебора за O(n²) к монотонному стеку за O(n), трассировка стека, ближайшие меньшие слева и справа, сведение матрицы из нулей и единиц к гистограммам.

12 мин чтенияалгоритмы · стек · python

Коротко

ПараметрЗначение
ЗадачиLeetCode 84 Largest Rectangle in Histogram, LeetCode 85 Maximal Rectangle
Главная идеякаждый столбец — высота прямоугольника; ширину ограничивают ближайшие меньшие столбцы
Инструментмонотонно возрастающий стек индексов
СложностьO(n)O(n) для гистограммы, O(R⋅C)O(R \cdot C) для матрицы
Типичный багзабыть «вытолкнуть» стек в конце — лечится нулевым столбцом-ограничителем

Общая техника монотонного стека и её простые применения разобраны в статье про монотонный стек. Здесь — две конкретные hard-задачи, которые на собеседованиях спрашивают чаще всего: почему решение работает, как его проверить на бумаге и как гистограмма превращается в решение для матрицы.

Постановка

Дан массив неотрицательных высот heights, ширина каждого столбца — 1. Найти площадь наибольшего прямоугольника, который целиком помещается в гистограмму.

Пример: [2, 1, 5, 6, 2, 3] → 10. Прямоугольник высотой 5 опирается на столбцы с высотами 5 и 6 (индексы 2 и 3), ширина 2.

Ещё несколько тестов, полезных для самопроверки:

heightsОтветПочему
[2, 4]4один столбец 4 или оба высотой 2 — одинаково
[3, 3, 3]9вся гистограмма
[2, 1, 2]3низкий столбец на всю ширину
[]0пустой вход
[1, 2, 3, 4, 5]9высота 3, ширина 3

Ключевое наблюдение

У любого прямоугольника в гистограмме высота равна высоте самого низкого столбца под ним. Иначе его можно было бы поднять выше.

Перевернём точку зрения: для каждого столбца i спросим, какой самый широкий прямоугольник имеет ровно его высоту. Он тянется влево, пока столбцы не ниже heights[i], и вправо — так же. Останавливают его ближайший меньший столбец слева L и ближайший меньший справа R:

area(i)=heights[i]⋅(R−L−1)\text{area}(i) = \text{heights}[i] \cdot (R - L - 1)

Ответ — максимум по всем i. Оптимальный прямоугольник обязательно найдётся среди этих n кандидатов, потому что его высота — высота какого-то столбца, а ширину он растягивает до упора.

Перебор за O(n²)

Перебираем левую границу i, двигаем правую j и поддерживаем минимум на отрезке:

def largest_rectangle_brute(heights: list[int]) -> int: best = 0 for i in range(len(heights)): low = heights[i] for j in range(i, len(heights)): low = min(low, heights[j]) best = max(best, low * (j - i + 1)) return best

Для n = 10^5 (ограничение LeetCode 84) это 5⋅1095 \cdot 10^9 шагов — не пройдёт. Но этот код пригодится как эталон для проверки быстрого решения на случайных тестах.

Два прохода: ближайшие меньшие слева и справа

Задача «для каждого элемента найти ближайший меньший» — классическое применение монотонного стека. Идём слева направо и держим в стеке индексы со строго возрастающими высотами. Перед тем как положить i, выбрасываем всех, кто не ниже heights[i]: для будущих элементов они уже не могут быть ближайшими меньшими, потому что i ближе и не выше. То, что осталось на вершине, — ответ для i.

def largest_rectangle_two_pass(heights: list[int]) -> int: n = len(heights) left = [-1] * n # индекс ближайшего меньшего слева right = [n] * n # индекс ближайшего меньшего справа stack = [] for i in range(n): while stack and heights[stack[-1]] >= heights[i]: stack.pop() left[i] = stack[-1] if stack else -1 stack.append(i) stack = [] for i in range(n - 1, -1, -1): while stack and heights[stack[-1]] >= heights[i]: stack.pop() right[i] = stack[-1] if stack else n stack.append(i) return max( (heights[i] * (right[i] - left[i] - 1) for i in range(n)), default=0 )

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

Если границ нет, используем «стены»: -1 слева и n справа. Тогда формула ширины R - L - 1 работает без особых случаев.

Один проход

Можно обойтись одним проходом. Заметим: когда столбец j выталкивается из стека текущим i, мы узнаём сразу обе его границы.

  • Правая: i — первый столбец справа, который ниже heights[j] (иначе j вытолкнули бы раньше).
  • Левая: элемент, оставшийся в стеке под j. Стек возрастающий, так что это ближайший слева меньший.

Значит, площадь для j можно посчитать прямо в момент выталкивания:

def largest_rectangle(heights: list[int]) -> int: stack = [-1] # индексы столбцов по возрастанию высот; -1 — левая стена best = 0 for i, h in enumerate(heights + [0]): # 0 в конце выталкивает всё while stack[-1] != -1 and heights[stack[-1]] >= h: height = heights[stack.pop()] width = i - stack[-1] - 1 best = max(best, height * width) stack.append(i) return best print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10 print(largest_rectangle([])) # 0

Два ограничителя делают код коротким:

  • -1 на дне стека — левая стена. Тогда stack[-1] после выталкивания всегда определён, и не нужна проверка «стек пуст».
  • 0 в конце массива — правая стена. Он ниже любого столбца и выталкивает всё, что осталось в стеке. Без него пришлось бы писать отдельный цикл после основного.

Трассировка на примере

heights = [2, 1, 5, 6, 2, 3], после добавления нуля индексы 0–6. Стек показываю без -1.

ihЧто выталкиваемШиринаПлощадьСтек после
02—[0]
110 (высота 2)1 - (-1) - 1 = 12[1]
25—[1, 2]
36—[1, 2, 3]
423 (высота 6)4 - 2 - 1 = 16
2 (высота 5)4 - 1 - 1 = 210[1, 4]
53—[1, 4, 5]
605 (высота 3)6 - 4 - 1 = 13
4 (высота 2)6 - 1 - 1 = 48
1 (высота 1)6 - (-1) - 1 = 66[6]

Максимум 10 появляется на шаге i = 4: столбец высотой 5 вытолкнут двойкой, слева под ним в стеке столбец высотой 1 с индексом 1, ширина 2.

Обратите внимание на столбец высотой 2 с индексом 4: его площадь 8 считается только в самом конце, когда его выталкивает ограничитель. Без нуля в конце этот кандидат потерялся бы.

Что с одинаковыми высотами

В коде условие >=: равные столбцы тоже выталкиваются. Тогда для первого из равных ширина посчитается заниженной — его правой границей станет равный ему сосед, а не настоящий меньший. Но это не страшно: последний столбец из группы равных получит правильную ширину, потому что под ним в стеке окажется настоящий меньший слева, а выталкивать его будет настоящий меньший справа. Ответ не меняется.

С условием > равные столбцы копятся в стеке, и уже первый из них при выталкивании получает полную ширину. Оба варианта корректны — главное понимать почему. Я сверил однопроходную версию, двухпроходную и перебор на трёх тысячах случайных массивов с повторами.

Сложность

Каждый индекс один раз попадает в стек и не больше одного раза из него выходит. Значит, суммарное число итераций while за весь проход — не больше n + 1, и общее время O(n)O(n), несмотря на вложенный цикл. Память — O(n)O(n) на стек: худший случай — возрастающий массив, где ничего не выталкивается до самого конца.

Для сравнения: есть решение «разделяй и властвуй» — найти минимальный столбец, посчитать прямоугольник на всю ширину и рекурсивно решить левую и правую части. В среднем O(nlog⁡n)O(n \log n), но на отсортированном массиве вырождается в O(n2)O(n^2), если искать минимум линейно. С деревом отрезков или разреженной таблицей для минимума получится честное O(nlog⁡n)O(n \log n). Стек проще и быстрее.

Maximal Rectangle: матрица из нулей и единиц

LeetCode 85. Дана матрица из '0' и '1'. Найти площадь наибольшего прямоугольника, состоящего только из единиц.

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Ответ — 6: строки 1–2, столбцы 2–4.

Трюк: зафиксируем нижнюю строку прямоугольника. Для каждого столбца посчитаем, сколько единиц подряд идёт вверх от этой строки. Получилась гистограмма! Наибольший прямоугольник из единиц, стоящий на этой строке, — это наибольший прямоугольник в гистограмме.

Высоты пересчитываются построчно за O(C)O(C): если в клетке единица, высота столбца растёт на 1, если ноль — сбрасывается.

СтрокаГистограммаЛучший прямоугольник
1 0 1 0 0[1, 0, 1, 0, 0]1
1 0 1 1 1[2, 0, 2, 1, 1]3
1 1 1 1 1[3, 1, 3, 2, 2]6
1 0 0 1 0[4, 0, 0, 3, 0]4
def maximal_rectangle(matrix: list[list[str]]) -> int: if not matrix: return 0 cols = len(matrix[0]) heights = [0] * cols best = 0 for row in matrix: for c in range(cols): heights[c] = heights[c] + 1 if row[c] == '1' else 0 best = max(best, largest_rectangle(heights)) return best matrix = [ ['1', '0', '1', '0', '0'], ['1', '0', '1', '1', '1'], ['1', '1', '1', '1', '1'], ['1', '0', '0', '1', '0'], ] print(maximal_rectangle(matrix)) # 6

Сложность — O(R⋅C)O(R \cdot C): R строк, на каждой пересчёт высот и проход стеком по C столбцам. Память O(C)O(C). Наивное решение — перебрать все пары углов и проверить заполненность — даёт O(R3C3)O(R^3 C^3) или, с префиксными суммами, O(R2C2)O(R^2 C^2); оно годится только как эталон для тестов. Я сверил решение со стеком с таким перебором на пятистах случайных матрицах.

Если строк намного больше, чем столбцов, матрицу выгодно транспонировать: стек тогда работает по короткой стороне, и память меньше.

Решение на JavaScript

function largestRectangleArea(heights) { const stack = [-1] let best = 0 for (let i = 0; i <= heights.length; i++) { const h = i === heights.length ? 0 : heights[i] while (stack.at(-1) !== -1 && heights[stack.at(-1)] >= h) { const height = heights[stack.pop()] best = Math.max(best, height * (i - stack.at(-1) - 1)) } stack.push(i) } return best } function maximalRectangle(matrix) { if (matrix.length === 0) return 0 const heights = new Array(matrix[0].length).fill(0) let best = 0 for (const row of matrix) { row.forEach((cell, c) => { heights[c] = cell === '1' ? heights[c] + 1 : 0 }) best = Math.max(best, largestRectangleArea(heights)) } return best } console.log(largestRectangleArea([2, 1, 5, 6, 2, 3])) // 10

В JS не стоит копировать массив через [...heights, 0] внутри maximalRectangle: на каждой строке это лишняя аллокация. Проверка i === heights.length делает то же без копии.

Не путать с Maximal Square

LeetCode 221 Maximal Square выглядит похоже, но решается проще — динамикой: сторона квадрата с правым нижним углом в (r, c) равна 1 + min из трёх соседей сверху, слева и по диагонали.

def maximal_square(matrix: list[list[str]]) -> int: rows, cols = len(matrix), len(matrix[0]) dp = [[0] * (cols + 1) for _ in range(rows + 1)] side = 0 for r in range(rows): for c in range(cols): if matrix[r][c] == '1': dp[r + 1][c + 1] = 1 + min(dp[r][c], dp[r][c + 1], dp[r + 1][c]) side = max(side, dp[r + 1][c + 1]) return side * side print(maximal_square(matrix)) # 4

Для прямоугольников такой переход не работает: у квадрата одна степень свободы (сторона), а у прямоугольника две, и «минимум из соседей» их не описывает. Обратное верно — решение для прямоугольников можно переделать под квадраты, взяв min(height, width) ** 2.

Типичные ошибки

  • Нет правого ограничителя. Возрастающий массив [1, 2, 3, 4, 5] вообще ничего не вытолкнет, и ответ будет 0. Нужен ноль в конце или цикл «доработки» стека.
  • Ширина i - j вместо i - stack[-1] - 1. Ширина считается от левого соседа в стеке, а не от выталкиваемого индекса: слева от j могли быть столбцы выше него, которые вытолкнули раньше. На [2, 1, 2] ошибка даст 2 вместо 3.
  • Значения в стеке вместо индексов. Без индексов ширину не посчитать.
  • Высоты в матрице не сбрасываются на нуле. Тогда «столбцы» проходят сквозь дыры, и ответ завышен.
  • Матрица из символов. В LeetCode 85 клетки — строки '1' и '0', а не числа. Сравнение row[c] == 1 тихо вернёт False везде.

Где встречается

LeetCode 84 и 85 — постоянные гости в списках hard-задач крупных компаний. Обычно ожидают:

  1. Наблюдение «высота прямоугольника — высота самого низкого столбца».
  2. Перебор за O(n2)O(n^2) как стартовую точку.
  3. Монотонный стек: два прохода или один с ограничителями.
  4. Аргумент, почему вложенный while даёт O(n)O(n).
  5. Для 85 — сведение к 84 построчно.

Та же идея «для каждого элемента найти ближайшие меньшие» решает Sum of Subarray Minimums (LeetCode 907) и подсчёт подматриц из единиц (LeetCode 1504). Похожие по духу задачи про площадь и высоты — Container With Most Water (там два указателя) и Trapping Rain Water, где тоже работает монотонный стек. Самая простая тренировка шаблона — Daily Temperatures.

Потренироваться в спокойной обстановке

Все задачи