Ссылка на задачу:
🔗 https://leetcode.com/problems/container-with-most-water
🏁 Задача номер 11 на LeetCode, Container With Most Water, — один из лучших примеров, где жадный оптимальный алгоритм обыгрывает наивный перебор. Она часто встречается в интервью (включая FAANG)
🧩 Условие задачи:
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
На русском:
Дан массив height[], где каждый элемент представляется как вертикальная линия на координатной плоскости. Нужно выбрать две такие линии и посчитать, какой максимальный объём воды между ними можно удержать. Объём ограничивается минимальной из двух высот и расстоянием между ними.
Пример:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Как получается результат?
Если взять линии с высотами height[1]=8 и height[8]=7, то расстояние между ними — 7, а минимальная высота — 7.
Объём (площадь) = 7 × 7 = 49 единиц воды.
🎯 Цель: найти такую пару линий, которая вместе образует «контейнер» с максимальной площадью.
Перед тем как посмотреть решение, подумайте как бы вы решали такую задачу?
Подписывайтесь на мой канал в Телеграмм, чтобы ничего не пропустить.
Ну или на канал в VK, если хотите видеть новые статьи у себя в ленте.
🧠 Наивный (но плохой) подход: перебрать все пары O(n²)
Можно было бы:
- пройтись по всем возможным парам (i, j)
- и для каждой пары посчитать площадь
- выбрать максимум
Но такой вариант имеет сложность O(n²), что станет непрактичным при больших n (до 10⁵), особенно в реальных задачах на собеседованиях и боевых системах.
—
🚀 Решение 1. Алгоритм двух указателей
📖 Как работает алгоритм?
- Изначально левый и правый указатели стоят на концах массива.
- На каждом шаге вычисляется текущая площадь = расстояние × мин(высота слева, высота справа).
- Далее, мы «двигаем» тот указатель, где высота меньше. Почему? Потому что максимум ограничен минимальной высотой. Если хотим больше объем, нужно надеяться на более высокую стенку с другой стороны.
- Повторяем, пока указатели не сойдутся.
⏱ Время: O(n), т.е. один проход по массиву
💎 Это уже оптимальное решение в большинстве случаев
Вот результат первого решения:
⚡ Решение 2. Ускорение — дополнение с оценкой высоты
🧠 В чём идея улучшения?
- Вместо того чтобы всегда проходить до конца, мы делаем "умную остановку".
- highest — это максимальная высота в массиве.
- На каждом шаге мы проверяем: теоретически, даже если по краям будет высота highest, но расстояние малое — мы всё равно не превысим max_area ➝ нет смысла продолжать.
- Если произведение highest × width < текущего максимума — прерываем.
⏱ В среднем эта оптимизация срабатывает быстрее, особенно когда максимум был найден ближе к началу, и оставшиеся координаты не имеют шанса его превзойти.
🔁 В худшем случае мы всё равно дойдём до конца, но в практических задачах алгоритм работает немного быстрее.
Вот результаты второго алгоритма:
📌 Вывод
Задача Container With Most Water является отличным примером того, как грамотное использование алгоритма двух указателей и жадной стратегии позволяет найти оптимальное решение без перебора всех вариантов.
Оба рассмотренных варианта работают за линейное время и эффективно справляются с задачей. Однако второе решение дополнительно использует эвристику: оно заранее оценивает, есть ли смысл продолжать поиск, и может завершиться раньше, что важно при работе с большими массивами.
Если вы изучаете алгоритмы или готовитесь к собеседованиям, эта задача — обязательный пункт в вашем репертуаре. Она не только тренирует мышление, но и помогает увидеть, как важно выбирать правильную стратегию.
🧠 Совет: попробуйте решить её без подсказок — и только потом сравните свой подход с представленным!
Спасибо, что прочли до конца 🙌
Подписывайтесь на мой канал в Телеграм или в VK — впереди ещё много интересного про ИИ, NLP и тестирование!
До встречи в следующих статьях! 💡