Всем привет, сегодня мы будем решать вот такую задачу
Казалось бы, что же тут такого сложного? Почему эта задача отмечена, как сложная?
И при этом её решило 58% тех, кто за неё взялся?
Ну что ж, приступим...
Начинаем обдумывать
Допустим, у нас есть вот такая таблица. Нам нужно найти идеальный алгоритм, который сможет быстро посчитать самый большой прямоугольник, состоящий из единичек.
Я уже имею опыт работы с двумерными массивами и знаю, что работа с элементами внутри одной строки будет быстрее, чем работа с элементами внутри одного столбца.
Дело в том, что двумерный массив состоит из одномерных массивов (ну или строк). Код получает элемент из памяти быстрее, если работать с ними в пределах одного массива (строки). Если работать сразу в разных строках например, считать по столбцу, так код будет работать менее быстро.
Постараемся придумать алгоритм. Чтобы лучше думалось, для примера, возьмём эту табличку (я сделал её в экселе)
Наши квадраты можно построить вот такими способами
Так... Я начал понимать... Я придумал.
Алгоритм такой. Сначала мы проходимся по всей возможной строке с единицами. Получается "3", записываем в переменную.
Дальше мы спускаемся на одну координату ниже. Считаем количество ячеек. Если оно будет такое же, как 3, тогда просто прибавляем к нашей 3. Если нет, то мы пересчитываем значение единиц для нового квадрата с размерами 2 на 2. Получится 4.
Идём дальше вниз. Если у нас тоже двойка, то просто считаем и добавляем единицы, получится 6. Потом снова спускаемся, там уже ширина 1. Пересчитаем количество единиц для прямоугольника 1 на 4, если оно будет больше, чем для 2 на 3, в нашу переменную с самым большим прямоугольником, какую-нибудь "max_rect" записываем число.
В первом случае мы выбрали самый первый квадрат, как точку, с которой всё начнётся. Дальше просто повторяем тот же алгоритм с другими квадратами по строке.
Ну а после этого можно перейти на следующую строку (Y) и начать сначала
Так. Я надеюсь, вы поняли ход моих мыслей. Вы же поняли?
Я пытаюсь реализовать алгоритм, который будет стараться больше передвигаться по строкам, чем по столбцам. Если коротко, мой алгоритм пытается из какой-то точки двигаться вправо-вниз, считать максимальное количество единичек в квадрате, а потом просто менять эту точку и начинать сначала.
Так. Ну в теории это вроде бы просто, а на практике то как?
Ничего, глаза боятся, а руки трясутся делают 😁👍
Приступаем к написанию кода
Для начала сделаю необходимые переменные
В процессе поймёте, что и куда. Я даже подписал их для вас.
Нам нужно сделать цикл, который останавливается, когда снизу и справа от выбранной ячейки нет 1. Там либо пустота, либо 0.
Так. Я написал вот такое сложное условие для цикла
У нас есть два условия, хотя бы одно из них должно выполняться. Если окажется, что Y в самом низу и не может больше опуститься, а у X впереди "стенка", то этот цикл завершается.
Обратите внимание, сначала идёт "y + 1 != rows", а потом "matrix[y + 1] != 0". Наш код не завершится ошибкой, если на последней строчке он попытается посчитать "matrix[y + 1]", он не выйдет за пределы массива, потому что перед ним стоит условие "y + 1 != rows". Это два условия, между которыми стоит "&&" (И), они должны быть выполнены оба. Если одно из них ложное, код не будет считать второе, соответственно за границы массива он не выйдет, и ошибки никакой не будет. Главное не перепутать последовательность.
Я искренне надеюсь, что вот эта длинная конструкция правильная. Но не исключаю, что придётся переделывать 😨...
Дальше реализовываем вот это, проходимся по строке.
Добавим ещё две переменные. Одна переменная будет хранить в себе единицы текущей строки, а вторая будет накапливать предыдущие. Потом по ходу развития кода увидите всё.
В общем, делаем код, который проходится по нашим единичкам. Но я очень не хочу всё делать на ощупь. Давайте попробуем ходя бы пройденные ячейки выводить через "console.log()".
Вот такой вывод
Если визуализировать то, что у нас получилось, получилось это. Бред какой-то. Даже близко не то...
Я понял, в чём ошибка. Наш код сначала прибавляет x, потом выводит новые координаты в консоль (поэтому не закрашена первая ячейка), а после этого считывает, какая ячейка будет следующей, и переносит на новый Y.
Если поставить вывод в консоль на первое место (на 18 строку) уже получается что-то более внятное. Но это всё ещё не то, что мы ожидаем.
Для начала добавим условие. Может быть такое, что наш код вообще начнётся в ячейке с нулём. Если такое будет, наш цикл должен выключиться
Мы сначала проверяем, можем ли мы двигаться, а уже потом прибавляем X, здесь я почему-то ошибся.
Ну а теперь получается вот так
Если визуализировать, получится вот так
Уже что-то более внятное, но здесь есть две ошибки:
1. Наша "оранжевая" область выходит за границы возможного прямоугольника. На координатах Y=0 и Y=1 ширина прямоугольника 1. Если считать по моему алгоритму, дальше, чем X = 0, она уходить не должна
2. Y не доходит до конца, X тоже.
Но сначала нужно разобраться с ошибкой 1.
Кстати, я намеренно не стал писать для неё условия, чтобы не усложнять картину раньше времени.
Вводим переменную "max_width" для ограничений по ширине, и только для начала делаем её Infinity, чтобы легче было её сравнивать.
Дальше в конце строки, сравниваем её длину с "max_width", если меньше, то в "max_width" записываем длину строки. А также делаем условие, которое не даёт выйти за эти ограничения.
В итоге получается так. Почти верно, но только по Y не достаёт до низа.
Я понял. Всё не так в условии. Условие нашего цикла и не даёт приблизиться к этой ячейке. Возможно, нам здесь понадобится цикл do while.
Я попробовал написать do while, но сайт начал баговаться, он начал решать только кейс с массивом [[1]], а предыдущий массив не хочет. Наш код пока не приспособлен к массиву [[1]], мы пока его тестируем на чём-то нормальном.
Да уж, ну и ну. Придётся делать.
Как выяснилось, в нашей задаче в массиве поступают не совсем числа, это строки. В предыдущих случаях они автоматически преобразовались в Number, но когда мы пытаемся сразу вывести matrix[0][0] через return, код даёт сбой.
Да. Наша площадка перестала баговаться и подкидывать только 3 кейс, мы снова можем проверять себя на первом кейсе.
Нет, do while не спасает. Вернёмся к обычному while.
Мне кажется, эти условия вообще надо убрать, и просто в while вставить 1 == 1, а сами проверки запихнуть по if внутри цикла для надёжности.
Ничего страшного, потом будем оптимизировать код и исправлять ошибки, если много нагородим 😁
Переносим все условия для Y в цикл. Условия для X переносить не нужно, они и так были, по сути они дублировались. Вот так вот, стало намного проще
И ошибка решилась 😁
Теперь нам надо сделать так, чтобы цикл начинался в разных точках. То есть цикл внутри цикла
Делаем два вложенных цикла и засовываем туда третий. (Ух, и долго же это придётся оптимизировать 😨)
Так, при помощи "console.log()" сейчас я посмотрю, правильно ли цикл проходится по нашим квадратам.
Один из примеров. Ну не правильно, он не должен выходить за правую стенку, в случае с жёлтым.
Я понял. Наша "max_width" объявляется вне двух важных циклов. Она должна каждую итерацию задаваться в "Infinity". Да и "this_len" (длина текущей строки) не обнулялась.
Задача достаточно сложная, здесь придётся всё по несколько раз проверять.
Ошибка не исчезла. У нас ещё ошибка здесь, мы не x должны сравнивать с max_width (x у нас смещается постоянно, а this_len)
Вот таким образом выделяются наши квадраты. Для удобства я разделил на несколько таблиц, не смогу же я их все одновременно разукрасить, и чтобы было понятно.
Если что, я данные с координатами вывожу через консоль, а разукрашиваю в Excel, чтобы вам было понятно 😁. А то подумаете, что я какие-то скрытые коды для отображения написал, и вам не показываю.
Ну, если у нас наш код так хорошо считает квадраты, тогда можно приступать к счёту единичек и выводу их из функции.
Переменная "previous_len" будет суммировать все единички полученного прямоугольника. После будет сравниваться с максимальным значением, и величина максимального прямоугольника будет выведена.
Да!! У нас получилось это сделать!!
Но я прекрасно понимаю, что здесь были лёгкие примеры. Мы ещё не проверили наш код на чём-то по-настоящему сложном!!
Ну что ж, спускаемся в ад 😈
Начинается жесть
И так, мы заглохли на этом примере.
Довольно миленько, учитывая, что это 55-ый тест из 76. Это удивительно.
Сейчас попробую отобразить в Excel, что же у нас произошло.
У нас неправильно посчитались элементы. Эх, а ведь хорошо, когда ты умный, и можешь выводить инфу через "console.log()", а после чего визуализировать её в экселе)) 😄
Это тот случай, который я рассчитал в начале, но не реализовал.
Нам нужно заменить это условие
Вместо проверки на 0 внизу ячейки, у нас будет проверка на 0 внизу ячейки, куда мы должны вернуться после этой "мини-итерации".
Попробую так
Выводит ошибку на 40-ом тесте
Но всё ещё хорошо.
Здесь ошибка. Нам не нужно проверять наличие нуля в этой ячейке, так как уже проверили там наличие единицы. Нам нужна именно следующая ячейка по X.
Не знаю, в чём дело? Может это потому, что уже поздний час, а я хочу спать?😴
Засиделся 😁
Так, хорошо. Мы добрались до этого момента. Я ждал, что так будет, настало время его исправлять.
Сделаем условие. Когда наш X подходит к концу, проверяем, меньше ли длина строки, чем наша максимальная длина? Если да, то сразу задаём её туда.
И после этого мы должны откусить этот лишний блок, и начать считать новый квадрат.
О ужас, что я написал? Неужели я так сильно хочу спать? Время 22:51 😨
Для этого мы должны рассчитать, какой путь он уже успел пройти со старой максимальной длиной.
Пишем условие. Если мы по Y отошли от нашей начальной точки (круг на картинке), то из нашей "previous_len" просто вычитается разница между старой и новой величиной, умноженной на количество строк.
Фуух... Ужас... 😨
Я представляю, что чувствуете вы, когда это смотрите. Возможно, вы просто в ужасе, и ничего не понимаете. Ну, я хотя бы картинками пытаюсь это понятнее объяснить...
62 теста из 77
На удивление, 62-ая задача точно такая же, но на этот раз она почему-то не прошла. Ох уж этот LeetCode, как он это делает?
У нас где-то потерялась единица, и я подозреваю виноват новый алгоритм для отсечения краёв.
С помощью "console.log()" я вывожу информацию вот в таком виде.
--- 0 0 | Означает новую точку для алгоритма (кружочек на схеме)
1 0 | Означает ячейку, через которую прошёл наш цикл
=== 20 | Означает запись значения самого большого прямоугольника.
Мы можем в этом коде также посмотреть, что именно у нас вычитается при обрезании краёв, и когда
Пусть это будет выглядеть так:
||| 2
По сути верно, отрезается 1 ячейка и 6 ячеек. Так, а вот на этом моменте я начал понимать. У нас было 21 ячейка, код перешёл на другую строку, обрезал ячейки и получил квадрат из 20 ячеек. Но квадрат с 21 ячейкой он, почему-то не записал...
А потому что он запись ведёт, когда этот цикл закончится (один из трёх вложенных, самый дальний (но самый первый))
После действий над previous_len в цикле можно добавить вот эту проверку
Так, а теперь мы на 71-ом кейсе. Здесь у нас уже время вышло, очень большой массив нам дали.
Подведём итоги
У меня почти получилось решить эту задачу уровня Hard. Код решает почти все кейсы, но он недостаточно оптимизирован.
Мне придётся разбить эту статью на две части, так как в одну статью на Яндекс Дзене может влезть максимум 100 скриншотов, а у меня их здесь около 70, я могу и не уложиться.
Надеюсь, вам понравилось. Подписывайтесь на канал и ставьте лайки...
Вторая часть: Продолжение (клик)