✓[LeetCode] 42. Trapping Rain Water

 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Constraints:

  ▷ n == height.length

  ▷ 1 <= n <= 2 * 104

  ▷ 0 <= height[i] <= 105

 

Example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
             In this case, 6 units of rain water (blue section) are being trapped.

 

 추상적인 개념만 잡히고 어떻게 문제를 풀지 가닥이 잡히지 않아 책을 봤지만.. 이해가 되지 않았다. 그래서 포인트를 이용한 문제해설 유튜브 영상까지 참고하면서 이해를 했다. 책을 끝까지 본 다음.. 다시 한번 돌아와서 풀어봐야겠다.. 아직도 추상적으로만 이해하고 있다.

class Solution:
    def trap(self, height: List[int]) -> int:
        
        if not height:
            return 0
        
        volume = 0
        
        # set the initial value
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        
        # loop for checking all and will be stopped if it's checked all
        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            
            # check min of max side toward max of max side
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        
        return volume