[LeetCode][Python3] 42. Trapping Rain Water

티스토리 메뉴 펼치기 댓글수0

프로그래밍/LeetCode

[LeetCode][Python3] 42. Trapping Rain Water

snoopybox
댓글수0

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 :

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

맨위로

https://www.snoopybox.co.kr/1966

신고하기