Задача “Container With Most Water” 150 000$ от Amazon — мое не стандартное решение
💧 Условие задачи: «Аквариум» (Container With Most Water) Представим, что нам дан массив целых чисел — например: [1, 8, 6, 2, 5, 4, 8, 3, 7] Каждое число в этом массиве символизирует высоту вертикальной стенки — как будто это столбец, воткнутый вертикально в пол. Все столбцы стоят на одной горизонтальной линии, то есть на «полу» (ось x), и находятся на равном расстоянии друг от друга. 📦 Теперь представим, что между этими столбиками можно налить воду — как будто мы смотрим на 2D-аквариум сбоку. 🧠 Цель задачи Найти две такие стенки (столбцы), которые, если между ними налить воду (по нижней границе — полу), смогут удержать наибольшее количество воды. 💧 Объём воды между двумя столбцами рассчитывается так: • Высота воды ограничена меньшей из двух стенок — потому что вода не может быть выше, чем самая низкая из них (иначе вытечет). • Ширина — это расстояние между этими двумя столбцами (в индексах). объём = (индекс_правой − индекс_левой) × min(высота_левой, высота_правой) Массив: [1, 8, 6, 2, 5, 4, 8, 3, 7] Индексы: 0 1 2 3 4 5 6 7 8 Столбцы (высоты): вертикальные стенки Пол: горизонтальная база (ось x) Вода: заливается между двумя стенками и держится на уровне самой низкой из них. Забегая вперед скажу 2. Классическое решение и его недостатки Обычно задача решается методом двух указателей с линейной сложностью. Однако этот подход не всегда даёт глубокую интуицию выбора стенок. ⸻ 3. Предложенный подход Я ввожу понятие энергоэффективной оценки каждой стенки: При этом: • Если стенка ближе к центру, её расстояние меньше — значит штраф за “удалённость” ниже. • Высокая, но далёкая стенка будет “наказана” в оценке. • Выбираются две стенки с максимальными result, а затем между ними вычисляется реальный объём воды. ⸻ 4. Обоснование устойчивости (пример) При наличии сильно асимметричного массива (например, левые элементы — [1, 2, 1], правые — [9, 8, 9]), алгоритм всё равно выбирает правые высокие значения, потому что они превосходят штраф и сохраняют высокий итоговый результат. ✔ Это делает алгоритм устойчивым к локальным аномалиям и не требует явно жёстких условий или вложенных циклов. ⸻ 5. Заключение Предложенный алгоритм демонстрирует новый взгляд на задачу через призму “выгодности” стенки, объединяя геометрическую и энергетическую оценку. Он сохраняет линейную сложность, но обладает дополнительной устойчивостью и хорошей визуальной интерпретацией. Разница:
https://habr.com/ru/articles/941446/
#алгоритмы #алгоритм #алгоритмы_поиска #алгоритмы_сортировки #алгоритмическая_торговля #алгоритмы_поиска_пути #лучшее #лучшие_практики #сложность_алгоритма #сложность_разработки
Habr
