Два указателя
Сбор дождевой воды
Найти сколько воды можно собрать после дождя
Постановка задачи
Описание (LeetCode)
Дан массив height из n неотрицательных целых чисел. Каждый элемент массива
показывает высоту столбца шириной 1.
После дождя вода может скапливаться между столбцами. Необходимо вернуть общее количество воды, которое можно собрать.
Пример 1:
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Результат:
6
Пояснение:
Вода скапливается в нескольких ямках между более высокими столбцами. Всего
получается 6 единиц воды.
Пример 2:
height = [4, 2, 0, 3, 2, 5]
Результат:
9
Ограничения:
n == height.length1 <= n <= 2 * 10⁴0 <= height[i] <= 10⁵
Решение
Это одна из самых популярных задач на два указателя. Она выглядит как задача про геометрию, но по сути проверяет, понимаете ли вы, от чего зависит добавляемое количество воды для текущей позиции массива.
Наивное решение для каждого индекса ищет максимальную высоту слева и максимальную высоту справа. После этого количество воды над текущим столбцом равно:
min(maxLeft, maxRight) - height[i]
Если для каждого элемента каждый раз заново искать максимум слева и справа, мы
получим O(n²). Можно улучшить это решение через два вспомогательных массива
leftMax и rightMax, но тогда понадобится O(n) дополнительной памяти.
Обычно на интервью просят оптимизировать решение: можно ли оставить время
O(n), но избавиться от дополнительных массивов?
Перейдите на Premium, чтобы продолжить
Разблокируйте доступ к этой статье и всем остальным материалам с NowInterview Premium
Перейти на Premium