[LeetCode][Python3] 42. Trapping Rain Water

Problem :

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

My Solution :

class Solution:

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

i, j = 0, len(height)-1

max_i = max_j = water = 0

while i < j:

if height[i] < height[j]:

max_i = max(max_i, height[i])

water += (max_i - height[i])

i += 1

else:

max_j = max(max_j, height[j])

water += (max_j - height[j])

j -= 1

return water

Comment :

양 끝에서 안쪽으로 포인터를 한칸씩 이동하며 물을 채운다. 매 회 이동할 포인터는 각 포인터 중 높이가 더 낮거나 같은 포인터를 선택한다. 왜냐하면 거기에 물을 채워도 반대쪽 포인터의 높이가 더 높거나 같기 때문에 방금 채운 물이 절대로 흘러내리지 않음을 보장받을 수 있기 때문이다.