给定建筑物高度的蓄水算法
给定建筑物高度的蓄水算法
提问于 2014-12-26 01:36:29
我在练习算法，在这个问题上我已经被困了几天了。当我测试我的解决方案时，我仍然是错误的。以下是问题陈述：
纽约的华尔街以其惊人的摩天大楼而闻名。但是雨季即将来临，今年建筑物上的水量将是巨大的。由于每座建筑物都粘在建筑物的左边和右边(第一座和最后一座除外)，只有当建筑物的高度高于建筑物左右的高度(华尔街边缘的高度为0)时，建筑物的水才会漏出。所有建筑物的宽度都是1米。你会得到华尔街建筑物从左到右的高度(以米为单位)，你的任务是按照标准输出(标准输出)打印华尔街建筑物上的总水量(以立方米计)。
示例输入：
heights: [9 8 7 8 9 5 6]示例输出：
5解释:在本例中，在第一座和第五座建筑之间有4立方米的水(1立方米在第2层，2立方米在第3层，1立方米在第4座)，在第5层和第7栋建筑之间有1立方米的水(超过第6栋)。
我处理这个问题的方法是找出全局最大值，并利用这些最大值中的差异来计算水的积累。我用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回答 5
Stack Overflow用户
回答已采纳
发布于 2014-12-26 21:18:10
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)-space算法基于stack-based solution求解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)结果是一样的。
Stack Overflow用户
发布于 2015-01-04 17:59:59
下面是一种只使用O(1)空间对刘志东和J.S.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两通解决方案基于以下逻辑：
- 找出整个图的最大峰值--全局最大值。
- 从左侧扫描到全局最大峰值。跟踪左边的最大值。每个单元格( a)低于或处于与左最大( b)位于左最大值()右侧的水平或与全局最大值()左侧的c( c)相同的水平上。当左边的最大值增加时，它对前面的列没有影响，但是后面的列在这个新的最大值级别上仍然有效。
- 从右边做同样的事情，相反。
这与Rémi的建议类似，但使用全局最大值来提供锚点，从而简化了工作。
单程解决方案部分是基于Mark Tolonen的思想。通过观察我们可以同时进行左、右传递，，而不知道全局最大，从而改进了上面的内容。这是因为两边的当前最大值要么大于，要么低于，或者等于另一边的最大值。下极大值总是低于全局最大值，即使我们还不知道全局最大值是什么，所以我们可以从那里到那边的下一个局部最大值。该算法非常详细：
- 从列表的
start和end的指针开始，将left_max、right_max和count初始化为0。 - 向右扫描，递增
start，直到达到左侧最大值为止。然后向左扫描，递减end，直到达到右侧最大值为止。 - 从较低的最大值开始，继续扫描，直到到达大于本地最大值的列为止，在此过程中计数可填充的单元格并将它们添加到
count。 - 重复步骤2和3，当
start和end重合时结束。
请注意，就我们的目的而言，局部最大值就是在上升之前的任何一点(可能是高原)，然后是下降。到目前为止所遇到的最高局部最大值以下的局部最大值仅在步骤3中遇到，在步骤3中它们没有效果。
最后一个解决方案可以在3秒内处理1000万个数据点：
>>> rands = [random.randrange(0, 1000000) for i in xrange(10000000)]
>>> %timeit fillcount(rands)
1 loops, best of 3: 3.3 s per loopStack Overflow用户
发布于 2014-12-26 01:55:26
class Solution:
# @param A, a list of integers
# @return an integer
def trap(self, A):
uTrapper = []
i = 0
leftIndex = 0
rightIndex = 0
# only 2 left could not trap water
while (i < (len(A) - 2)):
leftIndex = self.findLeftBank((A[i:])) + i
rightIndex = self.findRightBank((A[leftIndex+1:]), A[leftIndex]) + leftIndex + 1
uTrapper.append((A[leftIndex : rightIndex+1]))
i = rightIndex
return self.getRainWater(uTrapper)
def findLeftBank(self, list):
for i in range(len(list)):
curr = list[i]
currNext = list[i+1] if i+1 < len(list) else 0
if(curr > currNext):
return i
return len(list) - 1
def findRightBank(self, list, leftHight):
biggestLoc = len(list)
biggest = 0
for i in range(len(list)):
if(list[i] >= leftHight):
return i
if(list[i] > biggest):
biggestLoc = i
biggest = list[i]
return biggestLoc
def getRainWater(self, lists):
all = 0
for i in range(len(lists)):
list = lists[i]
height = min(list[0], list[len(list)-1])
for i in range(1, len(list)-1):
if(list[i] > height):
continue
all = all + (height - list[i])
return all
s = Solution()
print s.trap([9,6,8,8,5,6,3])上面没问题吧？
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27652073
复制相关文章
相似问题
腾讯云开发者
