Largest Rectangle in Histogram: решение монотонным стеком за O(n)

Разбираем задачу Largest Rectangle in Histogram: как найти максимальный прямоугольник в гистограмме с помощью монотонного стека за O(n). Объяснение и код C++.

Задача «Largest Rectangle in Histogram» из тех случаев, когда брутфорс кажется заманчивым, но прорыв происходит, когда переосмысливаешь цель. Секрет не в переборе всех возможных диапазонов и не в построении дерева решений. Вместо этого смотрим на каждый столбец и задаём один вопрос: если высота этого столбца — ограничивающая высота прямоугольника, насколько широко он может растянуться?

Задача в одном предложении

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

Наивный подход, который не укладывается по времени

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

class HistMax:
    def rect_max_area(self, bars: List[int]) -> int:
        best = 0
        def explore(pos, cur_min, span, arr):
            nonlocal best
            area_here = cur_min * span
            best = max(best, area_here)
            if pos < len(arr):
                if arr[pos] > cur_min:
                    explore(pos + 1, arr[pos], 1, arr)
                explore(pos + 1, min(arr[pos], cur_min), span + 1, arr)
        explore(0, float('inf'), 0, bars)
        return best

Ключевая идея

Цель проста: найти индекс, чья высота задаёт максимальный прямоугольник. Наибольший прямоугольник обязательно использует одну из существующих высот как ограничивающую. Для фиксированного индекса i с высотой heights[i] прямоугольник высоты heights[i] может расширяться влево и вправо, пока все столбцы не ниже heights[i]. Это естественным образом задаёт две границы: первый строго более низкий столбец слева и первый строго более низкий справа. Всё между этими двумя более низкими столбцами поддерживает прямоугольник высоты heights[i].

Отсюда важная формулировка: «Для каждого индекса i сохранить индексы первого столбца слева и справа, соответственно, который ниже, чем height[i]». Эти две границы определяют максимальную ширину, на которой heights[i] может выступать высотой прямоугольника. Зная такие границы для каждого i, остаётся посчитать площади всех кандидатов и взять максимум. Найти границы эффективно помогает монотонный стек.

Эффективное решение с монотонным стеком

Ниже — реализация со стеком индексов, поддерживающим неубывающую последовательность высот. Когда появляется более низкий столбец (или мы доходим до «сторожа» в конце), становится ясно, что у извлечённого индекса найден правый предел, а новый верх стека раскрывает левую границу. Ширина выводится из этих двух. Алгоритм работает за линейное время относительно числа столбцов.

class Histogram {
 public:
  int maxRectArea(vector<int>& bars) {
    int result = 0;
    stack<int> idxs;
    for (int p = 0; p <= bars.size(); ++p) {
      while (!idxs.empty() &&
             (p == bars.size() || bars[idxs.top()] > bars[p])) {
        const int h = bars[idxs.top()];
        idxs.pop();
        const int w = idxs.empty() ? p : p - idxs.top() - 1;
        result = max(result, h * w);
      }
      idxs.push(p);
    }
    return result;
  }
};

Почему границы так важны

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

Почему это полезно

Этот шаблон встречается во многих задачах по массивам, где требуется «первый меньший/больший слева/справа». Понимание приёма помогает распознать, когда монотонный стек может свернуть брутфорс до одного линейного прохода. На практике это разница между тайм-аутами и оптимальным решением.

Выводы

Сформулируйте цель так: выбрать индекс, чья высота даст максимальный прямоугольник. Для этого индекса определите, как далеко влево и вправо можно расширяться до первых строго более низких столбцов. Используйте монотонный стек, чтобы быстро найти эти границы и на лету посчитать лучшую площадь.