Наибольший прямоугольник в гистограмме и в матрице из единиц: монотонный стек
LeetCode 84 и 85 по шагам: от перебора за O(n²) к монотонному стеку за O(n), трассировка стека, ближайшие меньшие слева и справа, сведение матрицы из нулей и единиц к гистограммам.
Коротко
| Параметр | Значение |
|---|---|
| Задачи | LeetCode 84 Largest Rectangle in Histogram, LeetCode 85 Maximal Rectangle |
| Главная идея | каждый столбец — высота прямоугольника; ширину ограничивают ближайшие меньшие столбцы |
| Инструмент | монотонно возрастающий стек индексов |
| Сложность | для гистограммы, для матрицы |
| Типичный баг | забыть «вытолкнуть» стек в конце — лечится нулевым столбцом-ограничителем |
Общая техника монотонного стека и её простые применения разобраны в статье про монотонный стек. Здесь — две конкретные 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:
Ответ — максимум по всем 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) это шагов — не пройдёт. Но этот код пригодится как эталон для проверки быстрого решения на случайных тестах.
Два прохода: ближайшие меньшие слева и справа
Задача «для каждого элемента найти ближайший меньший» — классическое применение монотонного стека. Идём слева направо и держим в стеке индексы со строго возрастающими высотами. Перед тем как положить 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 )
Каждый индекс один раз кладётся и не больше одного раза снимается в каждом проходе, поэтому всё вместе — . Это решение проще всего объяснить, и с него разумно начинать на собеседовании.
Если границ нет, используем «стены»: -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.
i | h | Что выталкиваем | Ширина | Площадь | Стек после |
|---|---|---|---|---|---|
| 0 | 2 | — | [0] | ||
| 1 | 1 | 0 (высота 2) | 1 - (-1) - 1 = 1 | 2 | [1] |
| 2 | 5 | — | [1, 2] | ||
| 3 | 6 | — | [1, 2, 3] | ||
| 4 | 2 | 3 (высота 6) | 4 - 2 - 1 = 1 | 6 | |
| 2 (высота 5) | 4 - 1 - 1 = 2 | 10 | [1, 4] | ||
| 5 | 3 | — | [1, 4, 5] | ||
| 6 | 0 | 5 (высота 3) | 6 - 4 - 1 = 1 | 3 | |
| 4 (высота 2) | 6 - 1 - 1 = 4 | 8 | |||
| 1 (высота 1) | 6 - (-1) - 1 = 6 | 6 | [6] |
Максимум 10 появляется на шаге i = 4: столбец высотой 5 вытолкнут двойкой, слева под ним в стеке столбец высотой 1 с индексом 1, ширина 2.
Обратите внимание на столбец высотой 2 с индексом 4: его площадь 8 считается только в самом конце, когда его выталкивает ограничитель. Без нуля в конце этот кандидат потерялся бы.
Что с одинаковыми высотами
В коде условие >=: равные столбцы тоже выталкиваются. Тогда для первого из равных ширина посчитается заниженной — его правой границей станет равный ему сосед, а не настоящий меньший. Но это не страшно: последний столбец из группы равных получит правильную ширину, потому что под ним в стеке окажется настоящий меньший слева, а выталкивать его будет настоящий меньший справа. Ответ не меняется.
С условием > равные столбцы копятся в стеке, и уже первый из них при выталкивании получает полную ширину. Оба варианта корректны — главное понимать почему. Я сверил однопроходную версию, двухпроходную и перебор на трёх тысячах случайных массивов с повторами.
Сложность
Каждый индекс один раз попадает в стек и не больше одного раза из него выходит. Значит, суммарное число итераций while за весь проход — не больше n + 1, и общее время , несмотря на вложенный цикл. Память — на стек: худший случай — возрастающий массив, где ничего не выталкивается до самого конца.
Для сравнения: есть решение «разделяй и властвуй» — найти минимальный столбец, посчитать прямоугольник на всю ширину и рекурсивно решить левую и правую части. В среднем , но на отсортированном массиве вырождается в , если искать минимум линейно. С деревом отрезков или разреженной таблицей для минимума получится честное . Стек проще и быстрее.
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.
Трюк: зафиксируем нижнюю строку прямоугольника. Для каждого столбца посчитаем, сколько единиц подряд идёт вверх от этой строки. Получилась гистограмма! Наибольший прямоугольник из единиц, стоящий на этой строке, — это наибольший прямоугольник в гистограмме.
Высоты пересчитываются построчно за : если в клетке единица, высота столбца растёт на 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
Сложность — : R строк, на каждой пересчёт высот и проход стеком по C столбцам. Память . Наивное решение — перебрать все пары углов и проверить заполненность — даёт или, с префиксными суммами, ; оно годится только как эталон для тестов. Я сверил решение со стеком с таким перебором на пятистах случайных матрицах.
Если строк намного больше, чем столбцов, матрицу выгодно транспонировать: стек тогда работает по короткой стороне, и память меньше.
Решение на 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-задач крупных компаний. Обычно ожидают:
- Наблюдение «высота прямоугольника — высота самого низкого столбца».
- Перебор за как стартовую точку.
- Монотонный стек: два прохода или один с ограничителями.
- Аргумент, почему вложенный
whileдаёт . - Для 85 — сведение к 84 построчно.
Та же идея «для каждого элемента найти ближайшие меньшие» решает Sum of Subarray Minimums (LeetCode 907) и подсчёт подматриц из единиц (LeetCode 1504). Похожие по духу задачи про площадь и высоты — Container With Most Water (там два указателя) и Trapping Rain Water, где тоже работает монотонный стек. Самая простая тренировка шаблона — Daily Temperatures.