Python程序：计算雨水收集总量

假设我们有一个包含n个非负整数的数组。这些整数代表高度，每个柱的宽度为1，我们需要计算下雨后能够收集多少雨水。地图如下所示：

这里可以看到有8个蓝色方块，所以输出为8。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个栈st，water := 0，i := 0
  • 当i < height的长度时
    • 如果栈为空或height[栈顶] >= height[i]，则将i压入栈中，i加1
    • 否则
      • x := 栈顶元素，从栈中弹出栈顶元素
      • 如果栈不为空，则
        • temp := height[栈顶元素] 和 height[i] 的最小值
        • dist := i – 栈顶元素 – 1
        • water := water + dist * (temp – height[x])
  • 返回water

让我们来看下面的实现以更好地理解：

示例

在线演示

class Solution(object):
   def trap(self, height):
      stack = []
      water = 0
      i=0
      while i<len(height):
         if len(stack) == 0 or height[stack[-1]]>=height[i]:
            stack.append(i)
            i+=1
         else:
            x = stack[-1]
            stack.pop()
            if len(stack) != 0:
               temp = min(height[stack[-1]],height[i])
               dist = i - stack[-1]-1
               water += dist*(temp - height[x])
      return water
ob = Solution()
print(ob.trap([2,5,2,0,5,8,8]))

输入

[2,5,2,0,5,8,8]

输出

8

更新于：2020年10月20日

99 次查看

开启您的职业生涯

完成课程获得认证

开始学习
广告