Trapping Rain Water

Q: Какова временная сложность задачи Trapping Rain Water?

Решение с двумя указателями работает за O(n) времени и использует O(1) дополнительной памяти, поскольку на каждом шаге один указатель сдвигается внутрь. Вариант с массивами leftMax и rightMax также работает за O(n) времени, но использует O(n) памяти. Сканирование в обе стороны от каждого столбца занимает O(n²) .

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

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

Q: Чем задача Trapping Rain Water отличается от Container With Most 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, поэтому она означает 1. Получается 7.

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

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

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

Алгоритм

Установите 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. Третий проход применяет формулу.

Для [0, 3, 1, 0, 2, 5, 1, 2] уровни min(leftMax[i], rightMax[i]) равны [0, 3, 3, 3, 3, 5, 2, 2]. Если вычесть высоты, получится [0, 0, 2, 3, 1, 0, 1, 0], сумма которого равна 7. Время выполнения — O(n), но для этого нужны два массива из 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] — столбца справа от left. Значит, правая стенка для left не ниже leftMax, а уровень для него в точности равен leftMax, независимо от того, что находится между указателями. Если правый столбец ниже или равен левому, симметричное рассуждение определяет уровень для right.

Алгоритм

Установи left = 0, right = n-1, а leftMax, rightMax и water установи в 0.
Пока left < right: если height[left] < height[right], при необходимости увеличь leftMax до height[left], прибавь leftMax - height[left] и сдвинь left вправо.
Иначе сделай то же самое справа и сдвинь 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, количество воды становится отрицательным, и общая сумма уменьшается.
Перемещение указателя на более высокую колонку, уровень которой не доказан. На [4, 1, 3, 0, 5] эта версия возвращает 4 вместо 8.
Учет только ближайших соседей. В [3, 0, 2, 0, 1, 0, 4] колонка высотой 1 заполняется до уровня 3, заданного колонками, которые находятся в четырех и двух шагах от нее; ответ — 12.
Рассмотрение краев массива как стен. Вода стекает с них, поэтому одна колонка, две колонки или ряд, который только поднимается или только опускается, удерживает 0.

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

Какова временная сложность задачи Trapping Rain Water?

Решение с двумя указателями работает за O(n) времени и использует O(1) дополнительной памяти, поскольку на каждом шаге один указатель сдвигается внутрь. Вариант с массивами leftMax и rightMax также работает за O(n) времени, но использует O(n) памяти. Сканирование в обе стороны от каждого столбца занимает O(n²).

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

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

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

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

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

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод

Trapping Rain Water

Функция

Ограничения

Примеры

Подсказки

Решение

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

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

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

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

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

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