我正在练习算法，而我在这个问题上已经停留了几天。当我测试解决方案时，我仍然不正确。这是问题说明：
纽约华尔街以其惊人的摩天大楼而闻名。但是雨季即将来临，今年将要洒落在建筑物上的水量将会很大。由于每座建筑物都固定在其左右两侧的建筑物上（第一个和最后一个除外），因此，只有当建筑物的高度高于建筑物的高度时，水才可能从建筑物漏水。向左或向右（华尔街边缘的高度为0）。所有建筑物的宽度均为1米。您将获得从左到右的华尔街建筑物的高度（以米为单位），并且您的任务是将华尔街建筑物上所保持的总水量（以立方米为单位）打印到标准输出（标准输出） 。
输入示例：
heights: [9 8 7 8 9 5 6]
输出示例：
5
说明： 在此示例中，在第一座和第五座建筑物之间有4立方米的水（第二座是1立方米，第二座是3立方米，第四座是1立方米），第五到第七座建筑物之间是1立方米。立方米的水（在第六座建筑物上）。
我解决这个问题的方法是找到全局最大值，并使用这些最大值中的差异来计算水的累积量。我使用local_water变量说明了最后可能会错过的水。谁能帮助我找到算法或代码中的错误？
注意：我正在寻找一个只能通过每个元素一次的解决方案
这是我有错误的输入：
heights: [8,8,4,5]
这个输入应该产生1，而不是我的答案是0。
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
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
这是一种基于堆栈的解决方案的单遍（！）（O（n）次）O（n）空间算法，用于在直方图问题下最大化矩形区域：
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
例：
>>> 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
我已经针对蛮力O（n * m）算法进行了测试：
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
在哪里max_water_heldover_bruteforce()：
max_water_heldover_bruteforce()
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)
结果是相同的。
