Largest Rectangle in Histogram

Прямоугольник покрывает последовательность соседних столбиков от start до end, а его высота ограничена высотой самого низкого столбика в этой последовательности. Поэтому попробуй все последовательности. Зафиксируй start, затем увеличивай end на один столбик за раз и отслеживай минимальную высоту, встреченную на данный момент. Площадь наибольшего прямоугольника для этой последовательности равна lowest × (end-start+1).

В [2, 5, 6, 3, 4, 1] начни с 5. Для последовательностей получаются площади 5 × 1 = 5, затем 5 × 2 = 10 с 6, потом 3 × 3 = 9, когда добавляется 3, 3 × 4 = 12 с 4 и 1 × 5 = 5 с 1. Ответ — 12. Обновление lowest по мере роста последовательности позволяет выполнять каждый шаг за O(1), поэтому тебе не нужно заново просматривать последовательность, чтобы найти её минимум.

Алгоритм корректен, потому что каждый прямоугольник располагается над некоторой последовательностью, а для фиксированной последовательности самый высокий подходящий прямоугольник имеет высоту, в точности равную высоте самого низкого столбика. Алгоритм медленный, потому что существует n(n+1)/2 последовательностей: около 2 × 10^8 для 2 × 10^4 столбиков, и это количество никак не зависит от их высоты. Многие из этих последовательностей обрываются из-за низкого столбика задолго до конца, но алгоритм полного перебора всё равно продолжает их расширять.

Изменим подход к поиску. В наилучшем прямоугольнике хотя бы один столбец под ним имеет высоту, в точности равную высоте прямоугольника; иначе прямоугольник можно было бы поднять. Значит, ответ — максимум среди всех столбцов i площади прямоугольника высотой ровно heights[i], который может быть как можно шире. Он простирается, пока с каждой стороны не встретит столбец строго меньшей высоты. Назовём их индексы left[i] и right[i], а если таких столбцов нет, используем -1 и n. Прямоугольник покрывает столбцы строго между ними: ширина right[i]-left[i]-1. Так мы получаем n кандидатов вместо n²/2.

Чтобы найти left[i] для каждого столбца, пройдём слева направо со стеком индексов, высоты столбцов которых строго возрастают от дна к вершине. Когда встречается столбец i, удаляем из стека все индексы столбцов, высота которых не меньше heights[i]. Эти столбцы уже никогда не смогут быть ближайшими столбцами меньшей высоты ни для i, ни для любого столбца после него, потому что i ближе и не выше. Оставшийся на вершине индекс — ближайший слева столбец меньшей высоты. Затем добавляем i в стек. Такой же проход справа налево даёт right[i].

Для [2, 5, 6, 3, 4, 1] проходы дают left = [-1, 0, 1, 0, 3, -1] и right = [5, 3, 3, 5, 5, 6]. Столбец высоты 3 с индексом 3 ограничен столбцом высоты 2 с индексом 0 и столбцом высоты 1 с индексом 5, поэтому его прямоугольник имеет площадь 3 × (5-0-1) = 12. Столбец высоты 6 зажат соседями, и площадь его прямоугольника равна только 6 × 1.

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

При проходе слева направо уже видна каждая правая граница, но она отбрасывается. Когда столбец i удаляет столбец t, heights[i] не выше, чем heights[t], поэтому i — место, где прямоугольник столбца t заканчивается справа. А индекс, оставшийся под t в стеке, указывает, где он заканчивается слева. Поэтому измеряй прямоугольник в момент удаления: heights[t] × (i - below - 1), где below — новая вершина стека или -1, если стек теперь пуст.

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

Рассмотрим [2, 5, 6, 3, 4, 1]. Добавь в стек 2, 5 и 6: в стеке находятся индексы [0, 1, 2]. Число 3 с индексом 3 удаляет 6 (площадь 6 × (3-1-1) = 6) и 5 (площадь 5 × (3-0-1) = 10), затем останавливается на 2 и добавляется в стек. Добавь 4. Число 1 с индексом 5 удаляет 4 (площадь 4), затем 3, прямоугольник которого тянется от индекса 1 до 4: 3 × (5-0-1) = 12. Оно удаляет и 2 (2 × 5 = 10; стек пуст, поэтому ширина равна 5). Завершающий 0 удаляет 1 (1 × 6 = 6). Максимальная площадь равна 12.

Удаление при условии >= означает, что равный по высоте столбец может преждевременно остановить другой столбец. Это безопасно: равный столбец занимает его место в стеке, наследует ту же левую границу, а при последующем удалении его прямоугольник охватывает весь ряд. Для [3, 3, 3, 3] первые три столбца высотой 3 задают ширину 1, 2 и 3, а последний удаляется завершающим 0 с шириной 4, что даёт 12.