Python 中的雨水收集

假设我们有一个包含 n 个非负整数的数组。这些代表一个海拔图，其中每个条的宽度为 1，我们需要计算下雨后它能够积聚多少水。因此，地图将类似于 -

在这里我们可以看到有 6 个蓝色方块，所以输出将是 6。

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

  • 定义一个栈 st，water := 0 和 i := 0

  • 当 i < height 的大小

    • 如果栈为空或 height[栈顶] >= height[i]，则将 i 推入栈，i 加 1

    • 否则

      • x := 栈顶元素，从栈中删除栈顶

      • 如果栈不为空，则

        • temp := height[栈顶元素] 和 height[i] 的最小值

        • dest := 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([0,1,0,2,1,0,1,3,2,1,2,1]))

输入

[0,1,0,2,1,0,1,3,2,1,2,1]

输出

6

更新于: 2020-05-26

847 次浏览

开启您的 职业生涯

完成课程获得认证

开始学习
广告