Два указателя
Контейнер с водой
Найти две линии, которые вместе с осью X удерживают больше всего воды
Постановка задачи
Описание (LeetCode)
Дан массив целых чисел height длины n. Каждый элемент height[i] задает
высоту вертикальной линии, проведенной в точке i.
Нужно выбрать две линии так, чтобы вместе с осью X они образовали контейнер, который может удержать как можно больше воды. Верните максимальный объем воды, который может удержать такой контейнер.
Контейнер нельзя наклонять.
Пример 1:
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Результат:
49
Пояснение:
Максимальный контейнер образуют линии высотой 8 на индексе 1 и высотой 7
на индексе 8. Ширина контейнера равна 8 - 1 = 7, высота ограничена меньшей
линией 7, поэтому объем равен 7 * 7 = 49.
Пример 2:
height = [1, 1]
Результат:
1
Ограничения:
n == height.length2 <= n <= 10⁵0 <= height[i] <= 10⁴
Решение
Это одна из самых популярных задач на два указателя. На первый взгляд кажется, что нужно перебрать все пары линий: берем левую линию, затем пробуем каждую правую, считаем площадь и обновляем максимум.
Такой подход работает, но его сложность O(n²). Для n = 10⁵ это слишком
медленно. На интервью такой вариант можно озвучить как базовый, но после этого
нужно перейти к оптимизации.
Перейдите на Premium, чтобы продолжить
Разблокируйте доступ к этой статье и всем остальным материалам с NowInterview Premium
Перейти на Premium