[Python] Leetcode 42. 빗물 트래핑
Leetcode 42 Trapping Rain Water
문제
높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.
입력
height = [0,1,0,2,1,0,1,3,2,1,2,1]
출력
6
풀이
- 투포인터로 최대로 이동
- 오른쪽 최대값이 크면 왼쪽값을 이동, 왼쪽 최대값이 크며 오른쪽값을 이동
- 결과적으로 최대값에서 만난다.
- 시간복잡도 : O(N)
def trap(self, height: List[int]) -> int:
if not height:
return 0
volume = 0
left, right = 0, len(heights) - 1
left_max, right_max = heights[left], heights[right] # 3, 2
while left < right:
# 왼쪽, 오른쪽 최대값 갱신
left_max, right_max = max(heights[left], left_max), max(heights[right], right_max)
# 더 높은 쪽을 향해 투 포인터 이동
if left_max <= right_max:
volume += left_max - heights[left]
left += 1
else:
volume += righ_max - heights[right]
right -= 1
return volume
