Largest Rectangle in Histogram

Сложная№84возрастающий стек

Даны высоты столбиков, стоящих вплотную, ширина каждого 1. Найдите площадь самого большого прямоугольника, который помещается внутри них. Наш пример: [2, 5, 6, 3, 4, 1] даёт 12 — высота 3 над столбиками с индексами 1–4.

84 Largest Rectangle in HistogramРазбор · 1×

Пример: [2, 5, 6, 3, 4, 1]. В стеке индексы столбиков, высоты к верху растут; столбик меряют, когда его снимает более низкий. Пунктир — лучший прямоугольник на сейчас.

205162334415stack—
ещё не дошлистолбик iв стекепроверяемый или измеряемый столбикизмерен

Прямоугольников пока нет: best = 0

01/61
сначала · назад · пуск · шаг
Скорость
1function largestRectangleArea(heights):
2 best = 0
3 stack = empty stack // indices, rising heights
4 for i from 0 to len(heights): // one past the end
5 h = heights[i] if i < len(heights) else 0
6 while stack not empty and h < heights[top]:
7 bar = pop from stack
8 left = top + 1 if stack not empty else 0
9 area = heights[bar] * (i - left)
10 best = max(best, area)
11 push i onto stack
12 return best
состояние
best
0
stack
–
i
–
h
–
bar
–
left
–
area
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Самый большой прямоугольник высотой с самый низкий столбик под ним и может тянуться от этого столбика до первого более низкого с каждой стороны. Поэтому достаточно измерить каждый столбик один раз на всю эту ширину.
  2. Столбик снимает первый более низкий справа, на i. Под ним в стеке — первый более низкий слева: те, что между, были выше и уже сняты. Поэтому он тянется от left до i − 1.
  3. Лишний шаг с высотой 0 ниже любого столбика, поэтому в конце ни один не останется неизмеренным.

Сложность

Время O(n): каждый столбик кладётся один раз и снимается один раз, а каждое снятие меряется за O(1). Память O(n) на стек.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.