Место для подписи
На фотографию нужно поставить подпись так, чтобы она не легла на мелкие детали. Пиксели размечены: 1 — спокойный (яркость вокруг почти не меняется), 0 — нет. Найдите прямоугольник наибольшей площади со сторонами вдоль краёв снимка, все пиксели которого — единицы.
Тесты со второго по пятый — четыре фотографии автора сайта, уменьшенные до 300 пикселей в ширину. На «Воде и горах» лучшее место — полоса неба над горами, 217 × 36 пикселей.
Вход
В первой строке высота h и ширина w (1 ≤ h, w ≤ 600), дальше h строк из w символов 0 и 1.
Выход
Наибольшая площадь прямоугольника из единиц (0, если единиц нет).
Примеры
Пример 1
4 5 10100 10111 11111 10010
6
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Зафиксируйте нижнюю строку прямоугольника. Над каждым её пикселем — столбик единиц какой-то высоты. На что тогда похожа задача?
2Идея
Для каждой строки посчитаем высоты: сколько единиц подряд над каждым пикселем, считая его самого. Высоты пересчитываются из предыдущей строки за O(w). Прямоугольник с нижней стороной в этой строке — прямоугольник под гистограммой из этих высот, и наибольший такой находит монотонный стек.
3Разбор
Стек хранит столбики, высоты которых растут снизу вверх, и для каждого — где он начался слева. Новый столбик ниже вершины значит, что столбики выше него дальше вправо не продолжатся: снимаем их, считаем площадь «высота × ширина от начала до текущей позиции», а новый столбик наследует начало последнего снятого. В конце строки ставим столбик нулевой высоты, чтобы снять всё.
Каждый столбик ложится на стек и снимается по разу, поэтому строка обрабатывается за O(w), а весь снимок — за O(h·w).
3+Решение
4Сложность
O(h·w) времени и O(w) памяти.
5Типичные ошибки
- Расширять каждый столбик влево и вправо. Верно, но на гладком небе столбики одинаковы, и каждый расползается по всей строке: шестой тест из одних единиц — 600 строк по 600·600 шагов.
- Забыть столбик нулевой высоты в конце. Тогда прямоугольники, которые доходят до правого края, не будут посчитаны.
- Пересчитывать высоты заново. Высота над пикселем — высота над ним в предыдущей строке плюс один, если пиксель единица; иначе ноль.