我在练算法，这几天一直卡在这个问题上。当我测试我的解决方案时，我仍然不正确。这是问题陈述:

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.

示例输入:

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

最佳答案

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

这是基于 stack-based solution 的单遍 (!) (O(n) 时间) O(n) 空间算法对于Maximize the rectangular area under Histogram问题:

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() 是:

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)

结果是一样的。

关于python - 解决给定建筑物高度积水问题的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27652073/