[LeetCode][Python] 42. Trapping Rain Water

- 문제 링크: https://leetcode.com/problems/trapping-rain-water/

- 난이도: Hard

 

비가 왔을 때 얼마나 고이는지 푸는 문제다

투포인터, 공간복잡도는 O(1)로 풀 수 있는 문제다

 

일단 각 칸마다 물이 얼마나 찰 수 있는가? 생각해보면, 왼쪽 칸의 max, 오른쪽 칸의 max 중 더 작은 값에서 현재 칸의 높이를 빼면 된다

즉 min(leftMax, rightMax) - current가 된다.

현재 칸의 높이가 더 높을 수 있으니, 이 값이 양수인 때만 더해야 하는데, 이건 leftMax, rightMax 계산을 먼저 하면 굳이 안해도 된다

 

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]
        ret = 0

        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                ret += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                ret += rightMax - height[r]

        return ret