Комментарии 12
Спасибо, что поделились
Это классика литкода, задача 85. Решал когда-то. Объяснить решение O(n^2) проще всего, предварительно объяснив предыдущую задачу 84, оно в 85 используется как вспомогательная функция прямо без изменений.
Помню как на олимпиаде написал тупейшее решение с 4-мя вложенными циклами и прекрасно покатило.
С тех пор есть наглядный пример про ненужность предварительной оптимизации.
Главное суметь соптимизировать позднее по необходимости
ну здесь ограничений по времени нет, по крайней мере в этой задаче - мы демократично позволяем пользователям иногда посидеть часик-другой пока их решение считает - и подумать за это время, может что-то можно было сделать иначе :)
так и здесь - писать более или менее эффективное решение - это на выбор стреляющего. кому-то нравится по нескольку раз возвращаться к задаче и пытаться сделать быстрее, короче, изящнее. кто-то наоборот хочет просто побольше нарешать.
для оптимизации бывают специальные задачки в духе челленджей
найти прямоугольник без чёрных клеток максимальной площади
на сайте по ссылке под фразой "Answer should be a single value - size of the largest rectangle". Наверно подразумевается "Answer should be a single value - area of the largest rectangle"?
На первый взгляд линейная по памяти и времени от количества клеток. Нет?
Сложность измеряется от количества элементов, остальные метрики, могут быть только модификаторами. Выводя сложность от стороны, вы утверждаете что можете сделать за n^2 (цитирую: "N - Сторона матрицы") , где это соотвествует площади, то есть количеству элементов, а значит за 1 проход. Решение - в студию!
Да, за 1 проход. Нужно идя например по колонкам справа-налево одновременно поддерживать "кэшик" пустых клеток справа и использовать стек для хранения размеров прямоугольников (справа же). Думаю, как и я, вы можете это решение нагуглить :) Правда не скажу что в него легко вчитаться. Чтобы не совсем спойлить - оно на сайте drdobbs опубликовано плюс есть ссылка туда же со стековерфлоу где автор целиком реализацию написал.
В то же время, поскольку как вы справедливо замечаете, сторона матрицы это лишь квадратный корень от общего количества клеток, то решение за N^3 (или за C^3/2 если считать что C - количество клеток) не сильно хуже, но ощутимо проще.
Как уже говорил, надо сначала решить предыдущую задачу за O(n). Потом здесь поддерживать массив высот h длиной N, изначально с нулями. На очередной i-й строке сначала обновлять h (в цикле по столбцам, h[j] = a[i][j] == "белый" ? h[j] + 1 : 0), и вызывать решение предыдущей задачи для h.
Белый Прямоугольник (классическая задачка вместо приветствия)