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

Уолл-стрит в Нью-Йорке известна своими захватывающими дух небоскребами. Но сезон дождей приближается, и количество воды, которая будет падать на здания, будет огромным в этом году. Поскольку каждое здание прикреплено к зданиям слева и справа (кроме первого и последнего), вода может вытекать из здания только в том случае, если высота здания превышает высоту здания до его влево или вправо (высота краев Уолл-стрит равна 0). Все здания имеют ширину 1 метр. Вам даны высоты (в метрах) зданий на Уолл-стрит слева направо, и ваша задача - вывести на стандартный вывод (стандартный вывод) общее количество воды (в кубических метрах), удерживаемой над зданиями на Уолл-стрит ,

Пример ввода:

heights: [9 8 7 8 9 5 6]

Пример вывода:

5

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

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

ПРИМЕЧАНИЕ: я ищу решение, которое проходит через каждый элемент только один раз

Вот вход, где у меня есть ошибка:

heights: [8,8,4,5]

этот вход должен дать1не мой ответ, который0.

Вот мой код:

def skyscrapers(heights):
    heights.insert(0,0)
    heights.append(0)
    local_max = 0
    global_max = 0
    total_water = 0
    local_water = 0
    end_water = []
        # end_water records water heights to be used for finding 
                # water between the final global maximum and 
                # subsequent local maximums. These potential values are
                # stored in local_water.
    for i in range(1, len(heights)-1):
        end_water.append(heights[i]) 

        # check for local max
        if heights[i-1] < heights[i] and heights[i] > heights[i+1]:

            # record potential collected water for after final
            # gloabl max
            for s in end_water:
                local_water += (heights[i] - s) * (heights[i] - s > 0)
            local_max=i

        # new global max
        if heights[local_max] > heights[global_max]:
            for s in heights[global_max:local_max]:
                if heights[global_max] - s > 0:
                    total_water += heights[global_max] - s
            global_max = local_max
            local_water = 0
            end_water = []

    total_water += local_water

    print total_water