LeetCode42 - Trapping Rain Water

LC42 - Trapping Rain Water

Two Pointer

문제의 최대 높이는 3이지만 얼마나 높은지는 상관이 없다. 막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않는다.

최대 높이의 막대까지 각각 좌우 기둥 최대 높이 left_max, right_max와 현재 높이와의 차이만큼 물 높이 volume에 더해 나간다.

좌우 어느 쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 이동한다. 오른쪽이 크다면 left += 1, 왼쪽이 크다면 right -= 1로 이동한다.

class Solution:
    def trap(self, height):
        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 = max(height[left], left_max)
            right_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