Алгоритм решения для накопления воды с учетом высоты здания
Я практикую алгоритмы, и я застрял на этой проблеме в течение нескольких дней. Когда я проверяю свое решение, я все еще ошибаюсь. Вот формулировка проблемы:
Уолл-стрит в Нью-Йорке известна своими захватывающими дух небоскребами. Но сезон дождей приближается, и количество воды, которая будет падать на здания, будет огромным в этом году. Поскольку каждое здание прикреплено к зданиям слева и справа (кроме первого и последнего), вода может вытекать из здания только в том случае, если высота здания превышает высоту здания до его влево или вправо (высота краев Уолл-стрит равна 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