42. Trapping Rain Water (Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack)

링크 - https://leetcode.com/problems/trapping-rain-water/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

1) Two Pointers

1. left와 right를 각각 0, len(height) - 1로 초기화 한다. 또한 ans, left_max, right_max도 0으로 초기화한다.

2. left<right 일때 while문을 돌린다.

2.1 만약 height[left] < height[right]이면, 우리는 오른쪽의 기둥이 왼쪽보다 크다는 것을 알 수 있다. 따라서 왼쪽 기둥을 기준으로 그것보다 낮은 곳이 보인다면, 물이 고일수 있는 웅덩이가 되는 것이므로 이 웅덩이 크기를 ans에 더해준다.

2.2 만약 height[left] >= height[right]이면, 우리는 왼쪽의 기둥이 오른쪽보다 크다는 것을 알 수 있다. 따라서 오른쪽 기둥을 기중으로 그것보다 낮은 곳이 보인다면, 물이 고일수 있는 웅덩이가 되는 것이므로 이 웅덩이 크기를 ans에 더해준다.

3. 2를 반복하고 left >= right가 되면 답을 반환한다.

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        ans = 0
        left_max, right_max = 0, 0
        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                ans += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                ans += right_max - height[right]
                right -= 1
        return ans

Time Complexity: O(n)

Space Complexity: O(1)

2) Stack

1. 우리는 stack을 사용해서 왼쪽부터 오른쪽으로 가면서 답을 구할 것이다.

2. 만약에 stack에 값이 없으면, stack에 현재 인덱스값을 넣고 오른쪽으로 움직인다.

3. 만약에 stack에 값이 있고, 현재 height가 stack에 있는 peak 인덱스의 height보다 높으면, stack을 pop한다. 만약에 pop하고 나서 stack에 아무것도 없으면, 맨 왼쪽에 물을 담을 기둥이 없다는 뜻이므로 2번으로 간다.

4. 만약에 stack을 pop을하고나서 stack이 들어있다면, 우리는 물을 담을 수 있다. 따라서 (현재 인덱스 - stack의 peak의 값 - 1)을 통해 거리를 계산하고, 현재 height와 peak의 height중 작은 값에 pop한 인덱스를 빼면 물이 담길 높이가 계산이 된다. 이 둘을 곱해서 답에 더한다.

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        current = 0
        stack = []

        while current < len(height):
            while len(stack) != 0 and height[current] > height[stack[-1]]:
                peak = stack.pop()
                if len(stack) == 0:
                    break
                distance = current - stack[-1] - 1
                bounded_height = min(height[current], height[stack[-1]]) - height[peak]
                ans += distance * bounded_height
            stack.append(current)
            current += 1
        return ans

Time Complexity: O(n)

Space Complexity: O(n)