我正在练习算法,我已经坚持了几天这个问题.当我测试我的解决方案时,我仍然是错误的.这是问题陈述:
纽约华尔街以其令人叹为观止的摩天大楼而闻名.但是下雨的季节即将到来,今年将落在建筑物上的水量将会很大.由于每栋建筑物都被固定在左侧和右侧的建筑物上(除了第一个和最后一个),只有当建筑物的高度高于建筑物的高度时,水才会从建筑物中泄漏出来.向左或向右(华尔街边缘的高度为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, …