[LeetCode] 42. Traping rain water
투포인터를 이용해 물의 부피 더해간다.
left
와right
는 양 끝에서 시작하고left_max
와right_max
는 현재 위치의 높이와 기존의 최대값 중 더 큰 값이 됨.- 만약 오른쪽 최대값이 더 크다면 (왼쪽 최대값 - 왼쪽 현재값)을
volume
에 더하고left
는 오른쪽으로 이동(left += 1
) - 그렇지않으면, (오른쪽 최대값 - 오른쪽 현재값)을
volume
에 더하고right
는 왼쪽으로 이동(right -= 1
) - 두 포인터가 만날때까지 반복 --> 가장 높은 지점에서 만남
class Solution:
# 투포인터
def trap(self, height: List[int]) -> int:
if not height:
return 0
volume = 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
while left < right:
left_max, right_max = max(height[left], left_max), max(height[right], right_max)
if left_max <= right_max:
volume += left_max - height[left]
left += 1
else:
volume += right_max - height[right]
right -= 1
return volume
Author And Source
이 문제에 관하여([LeetCode] 42. Traping rain water), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gnlenfn/LeetCode-42.-Traping-rain-water저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)