用 Python 捕获雨水

pythonserver side programmingprogramming更新于 2026/1/15 6:04:17

假设我们有一个包含 n 个非负整数的数组。这些整数表示海拔图，其中每个条的宽度为 1，我们必须计算下雨后可以捕获多少水。因此地图将类似于 −

这里我们可以看到有 6 个蓝色框，因此输出将是 6。

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

定义一个堆栈 st，water := 0 和 i := 0
while i <高度的大小
- 如果堆栈为空或高度[堆栈顶部] >= 高度[i]，则将 i 推入堆栈，将 i 增加 1
- 否则
  - x := 堆栈顶部元素，从堆栈中删除顶部
  - 如果堆栈不为空，则
    - temp := 高度[堆栈顶部元素] 和高度[i] 的最小值
    - dest := i – 堆栈顶部元素 – 1
    - water := water + dist * (temp – height[x])
return 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]))