Trapping Rain Water

Q: Какова временная сложность задачи о накоплении дождевой воды?

Решение с двумя указателями работает за время O(n) и использует O(1) дополнительной памяти: на каждом шаге один указатель сдвигается внутрь, поэтому всего получается n-1 шагов. Вариант с массивами leftMax и rightMax тоже работает за время O(n) , но использует O(n) памяти. Сканирование обеих сторон для каждого столбца занимает O(n²) — около 4 × 10^8 операций чтения для 2 × 10^4 столбцов.

Q: Почему решение с двумя указателями может перемещать более короткую сторону?

Каждая уже пройденная колонка не выше большей из двух текущих колонок, поскольку перемещается только указатель, стоящий на более низкой колонке. Поэтому, когда левая колонка ниже, её текущий максимум не превышает высоту правой колонки, а справа от неё есть настоящая стенка. Уровень у левого указателя равен текущему максимуму независимо от того, что находится между указателями, поэтому можно зафиксировать эту колонку и двигаться дальше.

Q: Можно ли решить задачу о сборе дождевой воды с помощью стека?

Да. Храни стек индексов, высоты которых уменьшаются снизу вверх. Когда приходит столбик выше верхнего, извлеки верхний: это дно бассейна, стенками которого служат новый верхний элемент стека и текущий столбик. Добавь (min(two walls) - floor) × (distance between the walls - 1) и продолжай извлекать элементы, пока текущий столбик выше. Стек заполняет водой горизонтальные слои, а не столбцы, за время O(n) и с использованием O(n) памяти.

Q: Чем задача Trapping Rain Water отличается от Container With Most Water?

В задаче «Контейнер с наибольшим количеством воды» выбирают две линии, а линии между ними не занимают места, поэтому ответ — это один прямоугольник, самый большой. Здесь каждый столбец сплошной, вода находится поверх каждого столбца, а ответ — это сумма по всем столбцам. В обеих задачах используется два указателя, которые сдвигают сторону меньшей высоты, по одной и той же причине: результат для этой стороны уже определён.

СложноДва указателя Монотонный стек

+10

Ряд столбиков стоит бок о бок, ширина каждого — одна единица: height[i] — это высота столбика i. На ряд падает дождь, и вода скапливается в углублениях между столбиками. Вода остается над столбиком, только если слева и справа от него где-то стоят более высокие столбики; за первым и последним столбиками вода стекает.

Верните общее количество единичных квадратов воды, которое удерживает ряд.

Функция

trap(height: integer-array) → integer

heightinteger-array: высота каждого столбца, слева направо
Возвращаетinteger: общее количество единиц запертой воды

Ограничения

1 ≤ height.length ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵
Каждый столбик имеет ширину в одну единицу, и вода не задерживается за пределами первого или последнего столбика.

Примеры

Ввод: height = [0, 3, 1, 0, 2, 5, 1, 2]
Вывод: 7
Пояснение: Между 3 и 5 вода поднимается до уровня 3: она удерживает 2 единицы над столбцом высотой 1, 3 — над столбцом высотой 0 и 1 — над столбцом высотой 2. 1 ближе к концу находится между 5 и 2, поэтому уровень воды над ним равен 2, и он удерживает 1 единицу. 2 + 3 + 1 + 1 = 7.

+17 скрытых тестов при отправке

Дополнительный вопрос

Предположим, что столбцы образуют двумерную сетку высот и вода может вытекать во всех четырёх направлениях. Как тогда подсчитать объём запертой воды?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Количество воды над каждым столбцом зависит от столбцов, которые могут находиться далеко от него с обеих сторон, поэтому локальный просмотр соседей даёт неверный результат. Решение — одна формула: уровень воды над столбцом равен меньшему из двух значений — максимальной высоты столбцов слева от него и максимальной высоты столбцов справа от него. Поиск этих двух максимумов для каждого столбца занимает много времени, их сохранение в двух массивах обеспечивает линейную сложность, а два указателя, которые всегда перемещаются со стороны меньшей высоты, позволяют обойтись без массивов.

Просканируйте обе стороны каждого такта

Верно, но не успевает на самых больших тестах

Идея

Считай воду по столбцу за раз. Вода над столбцом i поднимается, пока не перельётся через более низкую из двух стенок. Левая стенка — самый высокий столбец от индекса 0 до i; правая стенка — самый высокий столбец от i до конца. Значит, уровень воды равен min(leftMax, rightMax), а количество воды над столбцом i равно этому уровню минус height[i].

Возьми массив [0, 3, 1, 0, 2, 5, 1, 2] и столбец высотой 0 с индексом 3. Самый высокий столбец слева имеет высоту 3, справа — 5. Уровень воды равен 3, значит, там находится 3 единицы воды. Для столбца высотой 1 с индексом 6 стенки имеют высоту 5 и 2: уровень воды равен 2, и столбец удерживает 1 единицу воды.

Оба прохода включают сам столбец i. Это не даёт ответу стать отрицательным: если столбец i выше всех столбцов с одной стороны, максимум с этой стороны равен его собственной высоте, уровень равен его высоте, и он удерживает 0 единиц воды. Поэтому первый и последний столбцы всегда удерживают 0 единиц воды.

Проблема — в стоимости. Для каждого столбца приходится просматривать весь ряд: половину слева и половину справа, поэтому общее число чтений равно n × n: 4 × 10^8 для 2 × 10^4 столбцов. Кроме того, проходы повторяют друг друга: самый высокий столбец слева от индекса 5 — это самый высокий столбец слева от индекса 4 плюс ещё одно сравнение, а при полном переборе он каждый раз вычисляется заново с нуля.

Алгоритм

Установи water равным 0.
Для каждого индекса i выполни поиск от 0 до i для определения leftMax.
Выполни поиск от i до последнего индекса для определения rightMax.
Добавь min(leftMax, rightMax) - height[i] к water.
Верни water.

def trap(height):
    n = len(height)
    water = 0
    for i in range(n):
        # The tallest bar at or left of i, and the tallest at or right of i.
        left_max = 0
        for j in range(i + 1):
            left_max = max(left_max, height[j])
        right_max = 0
        for j in range(i, n):
            right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

Заранее вычислите самую высокую планку с каждой стороны

Идея

Формула остаётся прежней; меняется только способ получить две стенки. Самый высокий столбец от 0 до i — это большее из самого высокого столбца от 0 до i-1 и height[i]. Поэтому один проход слева направо заполняет массив leftMax, вычисляя каждое значение на основе предыдущего. Один проход справа налево таким же образом заполняет rightMax. Третий проход для каждого столбца прибавляет min(leftMax[i], rightMax[i]) - height[i].

Для [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] и rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Меньшие из этих значений задают уровни [0, 3, 3, 3, 3, 5, 2, 2]. Вычтем высоты и получим [0, 0, 2, 3, 1, 0, 1, 0], сумма которых равна 7.

Каждый проход обрабатывает каждый столбец один раз, поэтому время работы составляет O(n): около 6 × 10^4 шагов для 2 × 10^4 столбцов вместо 4 × 10^8. Цена этого подхода — два дополнительных массива по n чисел. Именно с этой версии стоит начать на собеседовании: в ней трудно ошибиться, а следующий подход позволяет обойтись без массивов, не меняя самой идеи.

Алгоритм

Заполни leftMax слева направо: leftMax[0] = height[0], затем leftMax[i] = max(leftMax[i-1], height[i]).
Заполни rightMax справа налево: rightMax[n-1] = height[n-1], затем rightMax[i] = max(rightMax[i+1], height[i]).
Для каждого индекса добавь min(leftMax[i], rightMax[i]) - height[i] к общей сумме.
Верни общую сумму.

def trap(height):
    n = len(height)
    left_max = [0] * n   # tallest bar from index 0 to i
    right_max = [0] * n  # tallest bar from index i to n-1
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

Два указателя, которые перемещают нижнюю сторону

Идея

Для формулы нужна только более низкая из двух стен. Если можно доказать, что левая стена ниже правой на некотором индексе, стена справа от этого индекса вообще не нужна. Два указателя позволяют это доказать. Установи left на индекс 0, а right — на последний индекс, и отслеживай leftMax и rightMax — самые высокие столбцы, которые прошёл каждый указатель, включая столбец, на котором он стоит.

Инвариант: каждый столбец, который указатели уже прошли, не выше самого высокого из двух столбцов, на которых они стоят сейчас. Это верно, потому что ты всегда передвигаешь указатель, стоящий на более низком столбце, поэтому указатель проходит только столбец, который не выше столбца под другим указателем.

Теперь предположим, что height[left] < height[right]. Согласно инварианту, leftMax не больше height[right], а height[right] — это столбец справа от left. Значит, настоящая правая стена для left не ниже leftMax, а уровень воды на позиции left равен leftMax, что бы ни находилось между указателями. Добавь leftMax - height[left] и передвинь left на один шаг вправо. Когда height[right] — более низкий или равный по высоте столбец, сделай то же самое симметрично для правой стороны. Обнови текущий максимум перед добавлением воды, чтобы столбец под указателем считался собственной стеной, а количество воды никогда не было отрицательным.

Рассмотрим [0, 3, 1, 0, 2, 5, 1, 2]. Указатели начинают на 0 и 2: слева столбец ниже, он удерживает 0. Затем 3 против 2: ниже столбец справа, rightMax становится равным 2, он удерживает 0. Затем 3 против 1: столбец справа снова ниже, столбец высотой 1 удерживает 2-1 = 1. Затем 3 против 5: теперь ниже столбец слева, leftMax равен 3; столбец высотой 3 удерживает 0, столбец высотой 1 удерживает 2, столбец высотой 0 удерживает 3, а столбец высотой 2 удерживает 1. Указатели встречаются на столбце высотой 5. Итого получается 1 + 2 + 3 + 1 = 7 за один проход и с использованием четырёх переменных.

Алгоритм

Установите left = 0, right = n-1, а leftMax, rightMax и water равными 0.
Пока left < right, сравнивайте height[left] и height[right].
Если левая планка ниже, при необходимости увеличьте leftMax до height[left], прибавьте leftMax - height[left] и переместите left вправо.
Иначе при необходимости увеличьте rightMax до height[right], прибавьте rightMax - height[right] и переместите right влево.
Верните water, когда указатели встретятся; планка, на которой они встретятся, — самая высокая, и она ничего не удерживает.

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0  # tallest bar passed so far from each end
    water = 0
    while left < right:
        if height[left] < height[right]:
            # A bar taller than height[left] waits on the right, so left_max sets the level here.
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            # A bar at least as tall as height[right] waits on the left, so right_max sets the level.
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

Ловушки и крайние случаи

Формула короткая, и большинство неправильных ответов возникает из-за порядка двух строк или из-за того, какую сторону вы перемещаете.

Добавление воды до обновления текущего максимума. Если height[left] выше, чем leftMax, значение leftMax - height[left] будет отрицательным, и сумма уменьшится. Сначала увеличьте максимум, затем добавьте воду.
Перемещение указателя у более высокой стены. Уровень известен только со стороны более низкой стены; перемещая более высокую сторону, вы опираетесь на стену, которую ещё не проверили. Для [4, 1, 3, 0, 5] этот вариант возвращает 4 вместо 8.
Учитывание только ближайших соседей. Стены для столбца могут находиться далеко: в [3, 0, 2, 0, 1, 0, 4] столбец высотой 1 удерживает воду до уровня 3, заданного столбцами, отстоящими на четыре и два шага. Ответ здесь — 12.
Считать края массива стенами. Вода за первым или последним столбцом стекает, поэтому один столбец, два столбца или ряд, который только поднимается либо только опускается, удерживает 0 единиц воды.
Исключение столбца i из собственных проверок в решении методом перебора. Тогда столбец, который выше обеих сторон, даст отрицательное значение. Включите его в проверки или ограничьте результат снизу значением 0.
Переполнение в варианте с умножением. Здесь ответ достигает примерно 2 × 10^9 (два столбца высотой 10^5 и 19,998 пустых ячеек между ними), что всё ещё помещается в знаковое 32-битное целое число; в собственных вариантах используйте 64-битные суммы.

Частые вопросы4

Какова временная сложность задачи о накоплении дождевой воды?

Решение с двумя указателями работает за время O(n) и использует O(1) дополнительной памяти: на каждом шаге один указатель сдвигается внутрь, поэтому всего получается n-1 шагов. Вариант с массивами leftMax и rightMax тоже работает за время O(n), но использует O(n) памяти. Сканирование обеих сторон для каждого столбца занимает O(n²) — около 4 × 10^8 операций чтения для 2 × 10^4 столбцов.

Почему решение с двумя указателями может перемещать более короткую сторону?

Каждая уже пройденная колонка не выше большей из двух текущих колонок, поскольку перемещается только указатель, стоящий на более низкой колонке. Поэтому, когда левая колонка ниже, её текущий максимум не превышает высоту правой колонки, а справа от неё есть настоящая стенка. Уровень у левого указателя равен текущему максимуму независимо от того, что находится между указателями, поэтому можно зафиксировать эту колонку и двигаться дальше.

Можно ли решить задачу о сборе дождевой воды с помощью стека?

Да. Храни стек индексов, высоты которых уменьшаются снизу вверх. Когда приходит столбик выше верхнего, извлеки верхний: это дно бассейна, стенками которого служат новый верхний элемент стека и текущий столбик. Добавь (min(two walls) - floor) × (distance between the walls - 1) и продолжай извлекать элементы, пока текущий столбик выше. Стек заполняет водой горизонтальные слои, а не столбцы, за время O(n) и с использованием O(n) памяти.

Чем задача Trapping Rain Water отличается от Container With Most Water?

В задаче «Контейнер с наибольшим количеством воды» выбирают две линии, а линии между ними не занимают места, поэтому ответ — это один прямоугольник, самый большой. Здесь каждый столбец сплошной, вода находится поверх каждого столбца, а ответ — это сумма по всем столбцам. В обеих задачах используется два указателя, которые сдвигают сторону меньшей высоты, по одной и той же причине: результат для этой стороны уже определён.

Python

def trap(height):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

height = [0, 3, 1, 0, 2, 5, 1, 2]

Ожидается

Trapping Rain Water

Функция

Ограничения

Примеры

Подсказки

Решение

Просканируйте обе стороны каждого такта

Заранее вычислите самую высокую планку с каждой стороны

Два указателя, которые перемещают нижнюю сторону

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи