Код Senior Два указателя обновлено
Контейнер с водой
Условие
Массив высот стенок. Найди максимальную площадь воды между двумя стенками (площадь = min(высот) × расстояние).
Примеры
maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) // 49
maxArea([1, 1]) // 1
maxArea([]) // 0
Как подойти
Жадное сужение: ширина уменьшается всегда, значит увеличить площадь можно только за счёт высоты, а её ограничивает меньшая стенка - её и двигаем. O(n) вместо O(n²).
Подсказки: 2
- Начни с самых широких стенок.
- Двигать выгодно ту сторону, что ниже: только так есть шанс увеличить высоту.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.