Python中计算可以收集总降雨量的程序

假设我们有一个非负整数的数组n，它们代表每个条的高度，每个条的宽度为1，我们需要计算在降雨后它能收集多少水。因此地图将如下所示−

在这里，我们可以看到有8个蓝色的盒子，所以输出将是8。

为了解决这个问题，我们需要遵循以下步骤−

定义一个stack st，water: = 0和i: = 0
当 i <height的大小时
- 如果堆栈为空或height[stack top] >= height[i]，则将i推入堆栈，将i增加1
- 否则
  - x: =堆栈顶部元素，从堆栈中删除顶部
  - 如果堆栈不为空，则
  - temp：= height [stack top element]和height [i]的最小值
  - 目的地：= i-stack top element-1
  - water：= water + dist *（temp-height [x]）
返回water

让我们看以下实现以更好地理解−

更多Python相关文章，请阅读：Python 教程

例子

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]))