Условие
Bars of width 1 have the given heights. After rain, water collects above each bar up to the lower of the tallest bars on its left and right. Compute the total trapped water. An O(n) two-pointer solution is expected.
Implement trapped_water(heights).
Input
heights: Bar heights from left to right.
Output
Return the total units of water.
Ограничения
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
Примеры
Ввод:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Ожидаемый вывод:
expected = 6Ввод:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Ожидаемый вывод:
long long expected = 6;Ввод:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Ожидаемый вывод:
long expected = 6;Пояснение
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
Ввод:
heights = [3, 2, 1]
Ожидаемый вывод:
expected = 0Ввод:
std::vector<long long> heights = {3, 2, 1};
Ожидаемый вывод:
long long expected = 0;Ввод:
long[] heights = new long[] {3, 2, 1};
Ожидаемый вывод:
long expected = 0;Пояснение
Heights only go down, so water runs off: 0.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Уровень воды в каждой позиции ограничен более низкой из двух самых высоких границ слева и справа.
Подсказка 2
Отслеживайте границы с обоих концов, всегда двигая сторону с меньшей текущей границей.
Подсказка 3
Будьте внимательны к пустому вводу и плато одинаковой высоты; там воду определяет только меньшая сторона.
Ожидаемая сложность
время O(n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.