Гистограмма
Задача
У вас есть гистограмма - набор прямоугольников шириной $1$ и высотой $N$, идущих слева направо вплотную, причем они все "стоят" на земле - их нижняя координата $y$ равна $0$. Задача - найти наибольший по площади прямоугольник, лежащий внутри такой клеточной гистограммы.
Решение
Заметим, что нижняя граница наибольшего прямоугольника - это всегда $y = 0$. Наибольший прямоугольник должно быть невозможно рашсирить ни в одну из сторон. Давайте просто переберем все такие прямоугольники и выберем из них максимальный по площади.
Давайте идти слева направо по вертикальным прямоугольникам гистограммы и хранить такую "лесенку" - в стеке будут лежать пройденные столбики (индекс и высота), но только те, которые нужны, чтобы столбцы строго возрастали, и при этом лесенка заканчивалась последним рассмотренным столбцом.
Строить её нужно так: давайте рассмотрим новый столбец. Если его высота больше, чем у последнего в стеке (предыдущего столбца), то просто кладём его в стек, и на этом всё. Если его высота меньше или равна, чем у последнего, то нужно вынимать столбцы с конца стека, пока высота нового столбца не будет наконец больше, чем у последнего в стеке. В конце нужно просто вынуть все столбцы из стека (для этого удобно просто в конец положить фиктивный столбец высоты ноль).
При вынимании столбца из стека нужно посчитать площадь максимального прямоугольника, который включает этот столбец. Высоту мы уже знаем, надо определить его площадь. Заметим, что его левая координата - это индекс столбца, который лежит перед этим столбцом в стеке (это самый правый столбец, который левее удаляемого и при этом ниже по высоте) плюс один. А правая координата - это та, которую мы сейчас рассматриваем (раз нам нужно удалить этот столбец).
Как это работает? Наибольший прямоугольник упирается верхом хотя бы в один столбец, а значит когда мы его будем удалять, мы учтем этот прямоугольник.
Так можно за $O(N)$ найти площадь максимального прямоугольника в такой гистограмме.
Заметим, что к этой задаче можно свести задачу поиска максимального белого прямоугольника в прямоугольнике с черными и белыми прямоугольниками - нужно для каждой клетки посчитать, сколько клеток поряд наверх из нее - это белые клетки (с помощью простого динамического программирования), и после этого перебрать $N$ строк и решить задачу для гистограммы, низ которой является этой строкой - все высоты как раз мы теперь знаем.
Так мы решим эту задачу за $O(N^2)$ - а это размер прямоугольника, так что быстрее и не получится.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin