[LeetCode] 42. Trapping Rain Water (python)

https://leetcode.com/problems/trapping-rain-water/description/

Trapping Rain Water - LeetCode

 

 

투포인터를 이용한다는 건 알겠는데, 구현을 생각해내는게 어려운문제...

여기서 헷갈린건 왜 min pointer를 이동하지?라는 의문이었다.

이 문제는 투 포인터를 최대를 향해 이동시킨다.

즉, 더 높은 쪽을 향해 투포인터를 이동시켜야한다.

예를들어 left_max < right_max인 경우 right_max가 최대 높이일 확률이 있으니 left 포인터가 이동해야 한다.

 

 

---

SOLUTION CODE

# PYTHON

class Solution:
    def trap(self, height: List[int]) -> int:
        # 예외처리
        if not height:
            return 0
        
        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0

        while l < r:
            if leftMax < rightMax: # left가 작다면
                l += 1 # 최대를 향해 포인터 업데이트
                leftMax = max(leftMax,height[l]) # max값 update
                res += leftMax - height[l]

            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
                
        return res

 

- 직관적 코드

class Solution:
	def trap(self, height: List[int]) -> int:

		result = 0

		max_left = height[0]
		max_right = height[-1]

		start = 1
		end = len(height) - 2

		while start <= end:

			max_left = max(max_left, height[start])
			max_right = max(max_right, height[end])

			if max_left < max_right:
				result = result + max_left - height[start]
				start = start + 1
			else:
				result = result + max_right - height[end]
				end = end - 1

		return result