Задача про воду накапливающуюся в профиле острова

Question

Не могу понять как реализировать решение этой задачи.Я догадываюсь,что надо взять несколько самый высоких чисел,и уже от них вычитать меньшие числа,тем самым узнав воду.Но я не понимаю как это закодить на Python.

Компьютерная игра происходит в двумерном мире, который состоит из блоков 1 на 1 (метр). Острова игроков - это наборы столбцов различной высоты из блоков (камней). Во время сильных дождей все низины островов заполняются водой. По ландшафта островов, определите объем воды, который накапливается на каждом острове. Входные данные - стандартный ввод. Входные данные:

в первой строке записано натуральное число N (0 ≤ N ≤ 15) - количество столбцов, которые задают ландшафт острова.
во второй строке N натуральных чисел Hᵢ (0 ≤ Hᵢ ≤ 109 ) - высоты столбцов одного острова. Выходные данные:
выведите одно число - объем воды накопленный на данном острове (количество блоков занятых водой).

Input  
11  
2 5 2 3 6 9 3 1 3 4 6

Output  
18

Answer 1

Есть 2 указателя, левый и правый, идут навстречу друг другу.
Также храним известные нам максимумы, при проходе справа и слева.
Зная их, мы можем точно сказать, сколько воды остаётся в конкретном столбце.

def solve(profile):
    if not profile:
        return 0
    l, r = 0, len(profile) - 1
    max_l, max_r = profile[l], profile[r]
    water = 0
    while l < r:
        if max_l >= max_r:
            water += max_r - profile[r]
            r -= 1

            max_r = max(max_r, profile[r])
        else:
            water += max_l - profile[l]
            l += 1

            max_l = max(max_l, profile[l])

    return water


print(solve([101, 1, 1, 2, 1, 101])) # 399
print(solve([2, 5, 2, 3, 6, 9, 3, 1, 3, 4, 6])) # 18
print(solve([1, 2, 3, 4, -11019, 4, 3, 2, 1])) # 11023
print(solve([])) # 0

БЛОГ НА HUSL

Задача про воду накапливающуюся в профиле острова

Ответы (1 шт):