Container With Most Water (LeetCode 11) — Two Pointers на Go | Максимальный объём воды

Описание

В этом видео разбираем задачу LeetCode 11 “Container With Most Water”. Дана высота вертикальных линий height[i], нужно выбрать две линии так, чтобы вместе с осью X они образовали контейнер, в котором поместится максимально возможный объем воды.

Наивный перебор всех пар даёт сложность O(N²), но есть аккуратное решение за O(N) с помощью техники двух указателей (Two Pointers).

Идея алгоритма:
Ставим левый указатель в начало массива, правый — в конец. Это даёт максимальную ширину контейнера.

На каждом шаге считаем площадь area = (right - left) * min(height[left], height[right]) и обновляем максимум.

Двигаем ту стенку, которая ниже, потому что именно она ограничивает высоту воды. Сдвиг более высокой стенки не может увеличить площадь: ширина уменьшится, а высота всё равно ограничена меньшей стенкой.

Повторяем, пока указатели не встретятся.
Разбираем на примере height = [1,8,6,2,5,4,8,3,7], где оптимальный ответ — 49.

В видео:
- Интуитивное объяснение, почему жадная стратегия “двигать меньшую стенку” всегда корректна.
- Пошаговый разбор примеров и визуализация изменения площади.
- Реализация на Go с линейной сложностью и O(1) по памяти.