음이 아닌 정수 n개의 배열이 있다고 가정합니다. 이것들은 각 막대의 너비가 1인 높이를 나타냅니다. 우리는 비가 온 후 얼마나 많은 물을 잡을 수 있는지 계산해야 합니다. 따라서 지도는 다음과 같을 것입니다 -
여기에서 8개의 파란색 상자가 있는 것을 볼 수 있으므로 출력은 8이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 스택 st, water :=0 및 i :=0 정의
- i <높이의 크기
- 스택이 비어 있거나 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([2,5,2,0,5,8,8]))
입력
[2,5,2,0,5,8,8]
출력
8