给定建筑物高度的水累积算法

Question

我正在练习算法,我已经坚持了几天这个问题.当我测试我的解决方案时,我仍然是错误的.这是问题陈述:

纽约华尔街以其令人叹为观止的摩天大楼而闻名.但是下雨的季节即将到来,今年将落在建筑物上的水量将会很大.由于每栋建筑物都被固定在左侧和右侧的建筑物上(除了第一个和最后一个),只有当建筑物的高度高于建筑物的高度时,水才会从建筑物中泄漏出来.向左或向右(华尔街边缘的高度为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

Answer 1

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

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)

结果是一样的.

Answer 2

这是一个单程解决方案,通过仅使用O(1)空间改进了liuzhidong和JS Sebastian的解决方案:

def fillcount(elevations):
    start = 0
    end = len(elevations) - 1
    count = 0
    leftmax = 0
    rightmax = 0

    while start < end:
        while start < end and elevations[start] <= elevations[start + 1]:
            start += 1
        else:
            leftmax = elevations[start]

        while end > start and elevations[end] <= elevations[end - 1]:
            end -= 1
        else:
            rightmax = elevations[end]

        if leftmax < rightmax:
            start += 1
            while start < end and elevations[start] <= leftmax:
                count += leftmax - elevations[start]
                start += 1
        else:
            end -= 1
            while end > start and elevations[end] <= rightmax:
                count += rightmax - elevations[end]
                end -= 1

    return count

我针对这个更简单的双通解决方案进行了测试:

def fillcount_twopass(elevations):
    global_max = max(range(len(elevations)), key=lambda x: elevations[x])
    count = 0
    local_max = 0

    for i in xrange(0, global_max):
        if elevations[i] > local_max:
            local_max = elevations[i]
        else:
            count += local_max - elevations[i]

    local_max = 0
    for i in xrange(len(elevations) - 1, global_max, -1):
        if elevations[i] > local_max:
            local_max = elevations[i]
        else:
            count += local_max - elevations[i]

    return count

双程解决方案基于以下逻辑:

1. 找到整个图形的最大峰值 - 全局最大值.
2. 从左侧扫描到全局最大峰值.跟踪左边的最大值.每个单元格a)低于或等于左边最大值,b)左边最大值右边,c)左边是全局最大值,将保持水.当左边的最大值增加时,它对早期的列没有影响,但是后面的列现在将水保持在这个新的最大值.
3. 从右边做同样的事情.

这类似于Rémi所建议的,但使用全局最大值来提供锚点,这简化了事情.

一次性解决方案部分基于Mark Tolonen的想法.它通过观察我们可以同时执行左右传递而不知道全局最大值来改进上述内容.这是因为任何一方的当前最大值要么大于,低于要么等于另一方的最大值.即使我们还不知道全局最大值是多少,所以较低的最大值总是低于全局最大值,因此我们可以从那里继续到那一侧的下一个局部最大值.该算法详细说明:

1. 开始与指针start和end列表,并初始化left_max,right_max以及count对0.
2. 向右扫描,递增,start直到达到最大值.然后向左扫描,递减,end直到达到正确的最大值.
3. 从较低的最大值开始,继续扫描,直到达到大于局部最大值的列,沿途计算可填充单元格并将其添加到count.
4. 重复步骤2和3,结束时间start和end重合.

请注意,就我们的目的而言,局部最大值只是在上升之前的任何点(可能是一个高原),然后是下降.到目前为止遇到的最高局部最大值以下的局部最大值仅在步骤3中遇到,其中它们没有效果.

最后一个解决方案可以在3秒内处理一千万个数据点:

>>> rands = [random.randrange(0, 1000000) for i in xrange(10000000)]
>>> %timeit fillcount(rands)
1 loops, best of 3: 3.3 s per loop