42. Trapping Rain Water

LeetCode задача 42

Задача

Дан массив неотрицательных целых чисел, представляющих собой карту высот, где ширина каждой стойки равна 1. Вычислите, сколько воды может удерживать этот массив после дождя.

Подсказки

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

Подход

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

Алгоритм

1. Инициализируем переменную для хранения общего объема воды, который может быть удержан.
2. Пройдемся по массиву, для каждого элемента:
   • Найдем максимальную высоту слева и справа от текущего элемента.
   • Объем воды, который может быть удержан над этим элементом, равен минимальному значению из этих двух максимальных высот, минус высота самого элемента.
3. Добавим этот объем к общему объему.

Решение

def trap(height):
    n = len(height)
    # Инициализируем переменную для хранения общего объема воды
    total_water = 0
    
    for i in range(n):
        # Находим максимальную высоту слева от i
        max_left = max(height[:i + 1])
        
        # Находим максимальную высоту справа от i
        max_right = max(height[i:])
        
        # Объем воды для текущего элемента
        water = min(max_left, max_right) - height[i]
        
        # Добавляем этот объем к общему объему
        total_water += water
        
    return total_water