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

Arnab Chakraborty

更新於: 2020-05-26

847 次瀏覽

開啟您的 職業生涯

完成課程獲得認證

開始學習