算法来解决积水给建筑物高度积水、建筑物、算法、高度
我在练的算法，我一直停留在这个问题上几天。当我测试我的解决方案，我仍然不正确。这里的问题是语句：
华尔街在纽约以其惊人的摩天大楼。 但雨季将至，以及水的量 将翻倒的建筑将是巨大的这一年。以来 每一个建筑被套牢的建筑物其左侧和右 （除了第一个和最后一个），水可以从一个泄漏 建筑仅当建筑物的高度比高度高 建筑物其左边或其右侧（边缘的高度的 华尔街为0）。所有的建筑物具有1米的宽度。您 从给出的建筑物的高度（米）的华尔街 左到右，你的任务是打印到标准输出 举过（标准输出）的总水量（立方米） 华尔街的建筑物。
例输入：
高度：9 8 7 8 9 5 6]
示例输出：
5
说明： 在本实施例中，第一和第五建筑物之间有保持4立方米的水（1在第二，2在第三，和1比第四），和第五和第七建筑物之间存在1立方晶米持有（在第六楼）的水。
我的方法这一问题是要找到全局最大值，并使用在这些最大值的差异来计算水积聚。我占水我可能会错过在使用local_water变量结束。谁能帮我找到我的算法或code中的错误？
注：我在寻找一个解决方案，通过每个单元仅通过一次
下面是输入在那里我有一个错误：
高度：[8,8,4,5]
此输入应产生 1 ，不是我的回答是 0 。
下面是我的code：
高清摩天大楼（高度）：
heights.insert（0,0）
heights.append（0）
local_max = 0
global_max = 0
total_water = 0
local_water = 0
end_water = []
用于寻找＃end_water记录水的高度
最终的全球最大之间＃水
＃后面的局部最大值。这些潜在的值是
＃存储在local_water。
因为我在范围内（1，LEN（高度）-1）：
end_water.append（高度[我]）
＃检查本地最大值
如果高度[I-1];高度[i]和高度[Ⅰ]≥高度[I + 1]：
＃纪录的潜力收集水后的最终
＃gloabl最大
对于S在end_water：
local_water + =（高度[I] - S）*（高度[I] - S取代; 0）
local_max = I
＃新的全球最高
如果高度[local_max]≥高度[global_max]：
对于S在高度[global_max：local_max]：
如果高度[global_max] - S＆GT; 0：
total_water + =高[global_max] - S
global_max = local_max
local_water = 0
end_water = []
total_water + = local_water
打印total_water
解决方案
高度
_ _
9 | | _ _ | | _ _
8 | | _ | | | |
7 | | _ | |
6 | | _ | | | | _
5 | | | | _ | |
4 | | | | _ _
3 | | | | | | _ | |
2 | | | | | | _ | | _ | |
1 | 0 1 2 3 4 5 6 | | 0 1 2 3 | | 0 1 2 3 4 | POS
下面是一个单通（！）（O（N） - 时间）为O（n）空间的基础上堆栈算法基于解决方案为最大化直方图下的矩形区域的问题：
从收藏导入namedtuple
长城= namedtuple（'墙'，'POS高度）
高清max_water_heldover（高度）：
找到举行了摩天大楼与*高水的最大金额*。
堆栈= []
water_held = 0＃水缓缴的摩天大楼总量
适用于POS，高度历数（高度）：
而真正的：
如果不能叠加或高度＆LT;堆叠[-1] .height：＃下坡
stack.append（长城（POS + 1，高度））＃可能推左侧井壁
打破
其他：＃高度＆GT; =栈[-1] .height - 找到了合适的孔壁/底部
底部= stack.pop（）。高度
如果堆栈：＃如果有左孔壁
well_height = MIN（堆栈[-1] .height，高度） - 底部
如果well_height：
water_held + =（POS - 栈[-1] .POS）* well_height
返回water_held
例如：
＆GT;＆GT;＆GT; max_water_heldover（[9,8，7，8，9，5，6]）
五
＆GT;＆GT;＆GT; max_water_heldover（[8,8，4,5]）
1
＆GT;＆GT;＆GT; max_water_heldover（[3，1,2，1，3]）
五
我反对暴力O（N * M）算法进行了测试
从itertools进口产品
高清试验（max_buildings = 6，max_floors = 6）：
对于nbuildings，在产品nfloors（范围（max_buildings），范围（max_floors））：
在产品高度（范围（nfloors），重复= nbuildings）：
断言max_water_heldover（高度）== max_water_heldover_bruteforce（高度），高度
其中， max_water_heldover_bruteforce（）是：
进口SYS
从COLORAMA进口后退，脱颖而出，风格，INIT＃$ PIP安装COLORAMA
的init（带=不sys.stderr.isatty（））
高清max_water_heldover_bruteforce（高度）：
如果不高度：返回0
建筑，空气，水= ['B'，''，
Back.BLUE + Fore.WHITE +W+ Fore.RESET + Back.RESET + Style.RESET_ALL]
矩阵= [[水] * len个范围（高度）为_（MAX（高度））]
对于current_floor，在枚举摩天大楼（矩阵，启动= 1）：
外= TRUE
对于building_number，building_height在历数（高度）：
如果current_floor＆LT; = building_height：
外= FALSE
摩天大楼[building_number] =建筑
ELIF外：
摩天大楼[building_number] = AIR
对于我，building_height在枚举（逆转（高度），1）：
如果current_floor＆GT; building_height：
摩天大楼[-i] = AIR
其他：
打破
如果在sys.argv中--draw-摩天大楼：
打印（'\ n'.join（图（''加入，矩阵[:: - 1]）），文件= sys.stderr即可）
打印（ - * 60，文件= sys.stderr即可）
返回总和（在基质细胞在第1行的行，如果细胞==水）
的结果是相同的。
I am practicing algorithms, and I have been stuck on this problem for a few days. When I test my solution, I am still incorrect. Here is the problem statement:
The Wall Street in New York is known for its breathtaking skyscrapers. But the raining season is approaching, and the amount of water that will fall over the buildings is going to be huge this year. Since every building is stuck to the buildings to its left and to its right (except for the first and the last one), the water can leak from a building only if the height of the building is higher than the height of the building to its left or to its right (the height of the edges of Wall Street is 0). All the buildings have the width of 1 meter. You are given the heights (in meters) of the buildings on Wall Street from left to right, and your task is to print to the standard output (stdout) the total amount of water (in cubic meters) held over the buildings on Wall Street.
Example input:
heights: [9 8 7 8 9 5 6]
Example output:
5
Explanation: In this example, between the first and the fifth building there are held 4 cubic meters of water (1 over the second, 2 over the third, and 1 over the fourth), and between the fifth and the seventh building there is 1 cubic meter of water held (over the sixth building).
My approach to this problem is to find global maxima, and use differences in these maxima to calculate water accumulation. I account for water I might have missed at the end using the local_water variable. Can anyone help me find the error in my algorithm or code?
NOTE: I am looking for a solution which passes through each element only once
Here is the input where I have an error:
heights: [8,8,4,5]
this input should yield 1, not my answer which is 0.
Here is my code:
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
解决方案
height
_ _
9 | |_ _| | _ _
8 | |_| | | |
7 | | _ | |
6 | |_| | | | _
5 | | | |_| |
4 | | | | _ _
3 | | | | | | _ | |
2 | | | | | |_| |_| |
1 |0 1 2 3 4 5 6| |0 1 2 3| |0 1 2 3 4| pos
Here's a single-pass (!) (O(n)-time) O(n)-space algorithm based on the stack-based solution for Maximize the rectangular area under Histogram problem:
from collections import namedtuple
Wall = namedtuple('Wall', 'pos height')
def max_water_heldover(heights):
"""Find the maximum amount of water held over skyscrapers with *heights*."""
stack = []
water_held = 0 # the total amount of water held over skyscrapers
for pos, height in enumerate(heights):
while True:
if not stack or height < stack[-1].height: # downhill
stack.append(Wall(pos + 1, height)) # push possible left well wall
break
else: # height >= stack[-1].height -- found the right well wall/bottom
bottom = stack.pop().height
if stack: # if there is the left well wall
well_height = min(stack[-1].height, height) - bottom
if well_height:
water_held += (pos - stack[-1].pos) * well_height
return water_held
Example:
>>> max_water_heldover([9, 8, 7, 8, 9, 5, 6])
5
>>> max_water_heldover([8, 8, 4, 5])
1
>>> max_water_heldover([3, 1, 2, 1, 3])
5
I've tested it against a brute-force O(n*m) algorithm:
from itertools import product
def test(max_buildings=6, max_floors=6):
for nbuildings, nfloors in product(range(max_buildings), range(max_floors)):
for heights in product(range(nfloors), repeat=nbuildings):
assert max_water_heldover(heights) == max_water_heldover_bruteforce(heights), heights
where max_water_heldover_bruteforce() is:
import sys
from colorama import Back, Fore, Style, init # $ pip install colorama
init(strip=not sys.stderr.isatty())
def max_water_heldover_bruteforce(heights):
if not heights: return 0
BUILDING, AIR, WATER = ['B', ' ',
Back.BLUE + Fore.WHITE + 'W' + Fore.RESET + Back.RESET + Style.RESET_ALL]
matrix = [[WATER] * len(heights) for _ in range(max(heights))]
for current_floor, skyscrapers in enumerate(matrix, start=1):
outside = True
for building_number, building_height in enumerate(heights):
if current_floor <= building_height:
outside = False
skyscrapers[building_number] = BUILDING
elif outside:
skyscrapers[building_number] = AIR
for i, building_height in enumerate(reversed(heights), 1):
if current_floor > building_height:
skyscrapers[-i] = AIR
else:
break
if '--draw-skyscrapers' in sys.argv:
print('\n'.join(map(''.join, matrix[::-1])), file=sys.stderr)
print('-'*60, file=sys.stderr)
return sum(1 for row in matrix for cell in row if cell == WATER)
The results are the same.
