5. Largest Rectangle in Histogram

«Инвариант в алгоритме подобен закону сохранения в физике: пока он соблюдается, система предсказуема».
— Брайан Керниган

Наибольший прямоугольник в гистограмме (Largest Rectangle in Histogram): монотонный стек и поиск границ

Задача о наибольшем прямоугольнике в гистограмме (Largest Rectangle in Histogram, LeetCode 84) — вершина применения концепции монотонного стека (Monotonic Stack).
Дан массив целых неотрицательных чисел heights, представляющий высоты смежных столбцов гистограммы одинаковой ширины $1$. Требуется найти максимальную площадь непрерывного прямоугольника, который можно вписать в данную фигуру.

Наивный перебор всех возможных пар границ требует $O(N^2)$ времени. Использование монотонного стека сокращает время поиска до строгого линейного времени $O(N)$.

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["Итерация: i от 0 до N включительно (с фиктивным нулем на N)"]:::entry --> B{"Стек не пуст и<br/>heights[i] < heights[top] ?"}:::warning
    B -->|"Да"| C["Извлечь midIdx = stack.Pop()"]:::process
    C --> D["Вычислить ширину:<br/>width = i - stack.Top() - 1 (или i, если стек пуст)"]:::process
    D --> E["Площадь: area = heights[midIdx] * width<br/>maxArea = max(maxArea, area)"]:::process
    E --> B
    B -->|"Нет"| F["stack.Push(i)"]:::process
    F --> G{"i == N ?"}:::warning
    G -->|"Нет"| A
    G -->|"Да"| H["Возврат maxArea за O(N)"]:::success
  

1. Фундаментальный принцип: ограничение по наименьшему столбцу

Любой прямоугольник в гистограмме полностью определяется своим самым низким (лимитирующим) столбцом:

• Пусть $h = \text{heights}[i]$ — высота некоторого столбца.
• Этот столбец может быть распространен влево до первого столбца, чья высота строго меньше $h$.
• Этот столбец может быть распространен вправо до первого столбца, чья высота строго меньше $h$.

Таким образом, задача сводится к классической формулировке: для каждого элемента найти ближайший меньший элемент слева и ближайший меньший элемент справа.
Эту задачу монотонный стек решает ровно за один проход по массиву.

2. Инвариант монотонного стека

Стек хранит индексы столбцов.
Высоты столбцов по индексам в стеке образуют строго монотонно возрастающую последовательность:
$$\text{heights}[\text{stack}[0]] < \text{heights}[\text{stack}[1]] < \dots < \text{heights}[\text{stack}[\text{top}]]$$

Механика выталкивания

Когда мы рассматриваем текущий столбец $i$ и видим, что $\text{heights}[i] < \text{heights}[\text{top}]$:

1. Текущий индекс $i$ является правой границей для столбца на вершине стека (top). Правее индекса $i$ прямоугольник высоты $\text{heights}[\text{top}]$ продлить невозможно.
2. Новой вершиной стека после извлечения становится индекс левой границы (элемент, который строго ниже извлеченного).
3. Ширина вычисляется мгновенно:
   $$\text{width} = i - \text{newTop} - 1$$
   (а если стек опустел, прямоугольник простирается от самого начала: $\text{width} = i$).
4. Площадь: $\text{area} = \text{heights}[\text{mid}] \times \text{width}$.

3. Идиоматичная реализация на Go

package histogram

// LargestRectangleArea находит площадь максимального прямоугольника за O(N)
func LargestRectangleArea(heights []int) int {
    n := len(heights)
    if n == 0 {
        return 0
    }

    // Стек хранит индексы столбцов
    stack := make([]int, 0, n)
    maxArea := 0

    // Идем до n включительно (n — фиктивный нулевой sentinel)
    for i := 0; i <= n; i++ {
        curHeight := 0
        if i < n {
            curHeight = heights[i]
        }

        // Пока текущий столбец ниже вершины стека, выталкиваем и считаем площади
        for len(stack) > 0 && curHeight < heights[stack[len(stack)-1]] {
            midIdx := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // Pop

            h := heights[midIdx]
            width := i
            if len(stack) > 0 {
                leftBoundary := stack[len(stack)-1]
                width = i - leftBoundary - 1
            }

            area := h * width
            if area > maxArea {
                maxArea = area
            }
        }

        stack = append(stack, i) // Push
    }

    return maxArea
}

4. Сложность и Mechanical Sympathy

Анализ асимптотики:

• Время: строго $O(N)$. Несмотря на вложенный цикл for, каждый из $N$ индексов добавляется в стек ровно один раз и извлекается из него не более одного раза. Суммарное число операций со стеком $\le 2N$.
• Память: $O(N)$. В худшем случае (монотонно возрастающий массив) в стеке единовременно хранятся все индексы.

Локальность в кэше процессора

Стек реализован на базе предвыделенного среза make([]int, 0, n).

• Операции append и усечения stack[:len-1] не производят системных вызовов аллокатора кучи.
• Доступ к элементам среза происходит строго последовательно, что исключает промахи кэш-линий L1.

5. Вопросы для собеседования

Резюме

1. Монотонный стек позволяет за $O(N)$ времени найти ближайшие меньшие элементы с обеих сторон для всех элементов массива.
2. Использование фиктивного нуля на индексе $N$ устраняет необходимость в дополнительном коде очистки стека.
3. Реализация стека на плоском срезе с предвыделением памяти гарантирует отсутствие накладных расходов сборщика мусора Go.

В следующей статье мы применим монотонную очередь для поиска максимума в скользящем окне: 6. Sliding Window Maximum.