Pythonで雨水をトラップする

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

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

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

• スタックst、water：=0およびi：=0

  を定義します

• 私は<身長のサイズ

  • スタックが空または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([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