我一直在研究 problem 的不同算法在 Leetcode 上以 approach 1 开头.如果数组值是墙的高度,则该问题需要计算总水域面积(列宽 = 1)。
第一种方法找到每列左侧和右侧最大墙高的最小高度,如果列高度小于最小值,则将水添加到给定列的顶部。取最小值是因为这是收集到的水可以达到的最高值。要计算每边的最大值,需要对左侧和右侧进行 n-1
遍历。
我用 Python 编写代码,但这里是根据 Leetcode 上给出的解决方案用 C++ 编写的代码.
int trap(vector<int>& height)
{
int ans = 0;
int size = height.size();
for (int i = 1; i < size - 1; i++) {
int max_left = 0, max_right = 0;
for (int j = i; j >= 0; j--) { //Search the left part for max bar size
max_left = max(max_left, height[j]);
}
for (int j = i; j < size; j++) { //Search the right part for max bar size
max_right = max(max_right, height[j]);
}
ans += min(max_left, max_right) - height[i];
}
return ans;
}
我注意到在外循环迭代中左右列的最大值包括当前列。这样你可以获得的最低值为0。请确认这是正确的。我在 0
和要在我的代码中收集的 potentialWater
之间使用了 min()
。
我查看了代码并以我自己的方式重写了它,但我得到的是 0
,因为我收集的雨水总量应该是 6
。我的代码哪里出错了?
class Solution:
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if len(height) <= 2:
return 0
water = 0
for col in range(1, len(height)-1):
maxLeft = 0
maxRight = 0
for index in range(col):
maxLeft = max(maxLeft, height[index])
for index in range(col+1,len(height)):
maxRight = max(maxRight, height[index])
minHeight = min(maxLeft, maxRight)
# print(col, minHeight)
# minHeight = min(max(height[:col]), max(height[col+1:]))
potentialWater = minHeight - col
# print(potentialWater)
# water += potentialWater
water += max(0, potentialWater) # in case this is the highest column
return water
solution = Solution()
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(solution.trap(height))
最佳答案
简单的调试策略可以迅速将问题缩小到这一行:
potentialWater = minHeight - col
为什么要从最小高度中减去 number 列???这些根本不是同一类数量。相反,您想减去当前列的高度:
potentialWater = minHeight - height[col]
有了这个改变,我们得到了想要的输出:
$ python3 trap.py
6
正如已经指出的评论,您应该为此使用 Pythonic 编程习惯用法,例如替换
for index in range(col):
maxLeft = max(maxLeft, height[index])
for index in range(col+1,len(height)):
maxRight = max(maxRight, height[index])
与
maxLeft = max(height[:col])
maxRight = max(height[col+1:])
关于python - 收集雨水 : Bug in brute force approach,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50806917/