LeetCode День 3 Container With Most Water [Medium]⁠⁠

На этот раз будем считать аквариумы объем плоских аквариумов, а значит будет много воды.

Просто посчитать объемы всех возможных аквариумов и вернуть максимальное значение. На первый взгляд задача опять решается легко, но в прошлый раз тоже так казалось.

https://leetcode.com/problems/container-with-most-water/desc...

Собственно организуем вложенный цикл, где внешний перебирает все возможные левые стенки аквариума(т.е. кроме крайней правой), а внутренний перебирает все правые стенки аквариума(кроме крайней левой). Вуаля, и все с первого раза...

Я когда нажимал кнопку отправки решения, уже чувствовал, что получу ошибку. И таки да, как и в прошлый раз не хватает оптимизации...

Перенос тесткейса на локальную машину подсказал, что времени на обработку тратиться совсем не много, значит решение в принципе правильное, надо только ограничить количество итераций. Каюсь, сам изобрести ничего так и не смог, но в разделе Discussion, нашел хорошее предложение:

Основная мысль - это итерирование и сначала и с конца, т.е. мы для первого аквариума ставим крайние правую и левую границы, а затем смещаем их на встречу друг другу. Это даст нам уменьшение ширины аквариума на каждом шаге стабильно на единицу.

Но что же это значит? А значит это, что сдвигать надо всегда только меньшую по высоте сторону аквариума, потому что объем воды меряется как произведение меньшей по высоте стороны на ширину. Зафиксируем мысль, что если мы сдвигаем большую сторону аквариума, его объем точно уменьшиться, потому что ширина уменьшиться, и не важно что произойдет с высотой большей стороны, потому что считать объем мы все равно будем по меньшей. А этот расчёт для нас просто лишний, т.к. мы ищем максимальный объем аквариума. А это значит, что такой расчёт объема просто не нужно выполнять. Вот тут мы и сэкономим количество итераций.

Обратите внимание на картинку ниже, для обхода всех вариантов понадобилось всего 8 обсчётов объема, тогда когда как для первого решения это было бы 36 обсчётов(8 + 7 + 6 + 5 + 4 + 3 + 2 + 1). Да и увеличение числа границ на единицу для последнего решения увеличивает количество обсчётов всего на 1(линейная зависимость), тогда как для первого решения получается арифметическая прогрессия.

Все рассуждения выше подтвердились результатами:

От ChatGpt узнал, что это называется подход с двумя указателями решение в общем то идентично:

Сегодня было не сложно, пользоваться гайдами не стыдно, все уже изобретено до нас =)