[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

• 문제: Traping rain water