Python에서 빗물 가두기

n개의 음이 아닌 정수 배열이 있다고 가정합니다. 이것들은 각 막대의 너비가 1인 고도 지도를 나타내며, 우리는 비가 온 후 얼마나 많은 물을 가둘 수 있는지 계산해야 합니다. 따라서 지도는 다음과 같을 것입니다 -

여기에서 6개의 파란색 상자가 있는 것을 볼 수 있으므로 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 스택 정의, water :=0 및 i :=0

• 동안 나는 <높이의 크기

  • 스택이 비어 있거나 height[stack top]>=height[i]인 경우 i를 스택에 푸시하고 i를 1만큼 증가

  • 그렇지 않으면

    • x :=스택 상단 요소, 스택에서 상단 삭제

    • 스택이 비어 있지 않으면

      • temp :=높이[스택 상단 요소] 및 높이[i]

        의 최소값

      • dest :=i – 스택 맨 위 요소 – 1

      • 물 :=물 + 거리 * (온도 – 높이[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