[Algorithm] LeetCode #42 - Trapping Rain Water
개요
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.
Example 1:
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.
Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length0 <= n <= 3 * 1040 <= height[i] <= 105
각 칸마다 이동하면서 현재 높이와 양쪽 끝에서부터 셀 때 최대 높이의 차이만큼 물을 채웁니다. 양쪽 기둥 중 낮은 쪽을 계속 이동시켜서 비교합니다. 최대 높이인 지점에서 양쪽 기둥이 만납니다.
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
volume = 0
# two pointer
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
while left < right:
# update left_max, right_max
left_max, right_max = max(height[left], left_max), max(height[right], right_max)
# low side filled
if left_max <= right_max:
# update water height
# Up to the maximum height point, add water height:
# difference between the maximum height and the current height of the left and right columns
volume += left_max - height[left]
# move
left += 1
else:
volume += right_max - height[right]
# move
right -= 1
return volume
