Pythonで捕まえることができる雨の総量を見つけるためのプログラム

n個の非負の整数の配列があるとします。これらは、各バーの幅が1である高さを表しており、雨が降った後にどれだけの水を捕まえることができるかを計算する必要があります。したがって、マップは次のようになります-

ここでは、8つの青いボックスがあることがわかります。したがって、出力は8になります。

これを解決するには、次の手順に従います-

• スタックst、water：=0およびi：=0を定義します
• whilei<身長のサイズ
  • スタックが空またはheight[stacktop]> =height [i]の場合、iをスタックにプッシュし、iを1増やします
  • それ以外の場合
    • x：=スタックトップ要素、スタックからトップを削除
    • スタックが空でない場合は、
      • temp：=高さの最小値[スタックトップ要素]と高さ[i]
      • dest：=i –ス​​タックトップ要素– 1
      • 水：=水+距離*（temp – height [x]）
• 水を戻す

理解を深めるために、次の実装を見てみましょう-

例

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