[LEET CODE] 42. Trapping Rain Water

# Problem

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. Example 2: Input : height = [4, 2, 0, 3, 2, 5] Output : 9 Constraints: n == height.length 0 <= n <= 3 * 104 0 <= height[i] <= 105

# My Answer = Solution1

class Solution:
    def trap(self, height: List[int]) -> int:
        h = 0
        t = len(height)-1
        hmax = 0
        tmax = 0
        answer = 0
        while h < t:
            if height[h]<= height[t]:
                if height[h]>hmax:
                    hmax = height[h]
                answer += hmax-height[h]
                h += 1
            else:
                if height[t]>tmax:
                    tmax = height[t]
                answer += tmax-height[t]
                t -= 1
        return answer

 

# Solution 1 - 투 포인터를 최대로 이동

class Solution:
    def trap(self, height: List[int]) -> int:
        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, right_max = max(height[left], left_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

높이가 최대인 지점에서 left, right 가 만나게 됨

 

 

# Solution 2 - 스택 쌓기

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

        for i in range(len(height)):
            # 변곡점을 만나는 경우
            while stack and height[i] > height[stack[-1]]: # 이 부분 반복!!!!!
                # 스택에서 꺼낸다
                top = stack.pop()

                if not len(stack): # 스택이 비면 -> 길이가 0
                    break

                # 이전과의 차이만큼 물 높이 처리
                distance = i - stack[-1] - 1 # 인덱스는 0 부터 시작하므로 1을 더 빼줌
                waters = min(height[i], height[stack[-1]]) - height[top]

                volume += distance * waters

            stack.append(i)
        return volume

스택에 쌓아 나가면서 현재 높이가 이전 높이보다 높을 때 격차만큼 물 높이를 채운다

i	stack	height[i]	height[stack[-1]]	top	distannce	waters	volume
	[]						0
0	[0]	0	0
1	[]	1		0
	[1]		1
2	[1,2]	0	0
3	[1]	2	1	2	3-1-1 = 1	min(2,1)-0 = 1	+1
	[]	2		1
	[3]		2
4	[3,4]	1	1
5	[3,4,5]	0	0
6	[3,4]	1	1	5	6-4-1 = 1	min(1,1)-0 = 1	+1
	[3,4,6]		1
7	[3,4]	3	1	6	7-4-1 = 2	min(3,1)-1 = 0	0
	[3]	3	2	4	7-3-1 = 3	min(3,2)-1 = 1	+3
	[]	3		3
	[7]		3
8	[7,8]	2	2
9	[7,8,9]	1	1
10	[7,8]	2	2	9	10-8-1 = 1	min(2,2)-1 = 1	+1
	[7,8,10]		2
11	[7,8,10,11]	1					= 6

i = 7 일 때 while 문이 반복된다. -> 층별로 계산

현재 height가 3일 때, 이전 블록이 3일때, 2일 때 , 1일 때 

 

이전보다 높은 블럭일 때마다 계산 - > 지금 블럭과 사이에 빗물이 쌓일 수 있는 낮은 이전 블럭들을 스택에 넣음

 

water에서 낮은 벽까지만 빗물이 쌓일 수 있으므로 min(height[i],height[stack[-1]])

높은 벽 안에 낮은벽이 있어서 쌓일 수 있을 경우 맨 밑부터 계산 -> height[top]은 이미 계산되었으므로 빼준다.

 

ex) 2-1-0-3 의 경우

1	2	3	4

stack 에는 1,2가 들어있을 것임 (stack = [1,2]), top = 3

1) 먼저 2열과 4열 사이의 1칸 계산

     2열과 4열 중 낮은 2열의 높이 1, 3열(top)의 높이는 0이므로 계산할 높이는 1

 

stack = [1], top = 2

2) 1열과 4열 사이의 2칸 계산 (이때 top은 2열의 높이 = 1)

     이때 물이 채워질 수 있는 높이는 1열과 4열 중 낮은 1열 = 2

     2열과 같이 1열과 4열 사이에 더 낮은 높이의 블록이 있다면 1)에서 이미 계산되었으므로 전체 높이에서  그만큼의 높이 빼주기

     ----> 2*(2-1) = 1

 

ex) 3-1-0-1의 경우

stack 에는 1,2가 들어있을 것임 (stack = [1,2]), top = 3

1) 먼저 2열과 4열 사이의 1칸 계산

  2열과 4열 중 낮은 2열의 높이 1, 3열(top)의 높이는 0이므로 계산할 높이는 1-0 = 1

 

stack = [1], top = 2

2) 1열과 4열 사이의 2칸 계산

    1열과 4열의 높이가 같으므로 이때 물이 채워질 수 있는 높이  = 3

    2열과 같이 1열과 4열 사이에 더 낮은 높이의 블록이 있다면 이미 계산되었으므로 그만큼의 높이를 빼주어야 한다. (3-1 = 2)

     ----> 2*(3-1) = 4