Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/

📌 문제

위와 같이 기둥들이 있을 때, 빗물이 고이는 volume의 수를 세라.

( volume = 기둥 높이의 차이만큼 생긴다 )

📌 아이디어

max 값을 기준으로 왼쪽과 오른쪽이 나뉜다.
max 값을 향해 왼쪽과 오른쪽이 전진하는데, ( two poniter )
이 때 left 기준으로

left_max = max(left_max,heights[left])
left_max - heights[left] 의 값을 volume에 더해준다.

( max 값이 여러개여도 상관없다. 중요한건 max의 위치가 아니라, max 값을 기준삼아서 전진하고, 전진하면서 max값과 해당 기둥의 차이를 계산하는 것 )

📌 코드

def trap(heights):
    if not heights:
        return 0

    volume = 0
    left=0
    right = len(heights)-1

    left_max = heights[left]
    right_max = heights[right]

    while left<right:
        left_max = max(heights[left,left_max])
        right_max = max(heights[right,right_max])

        if left_max<=right_max:
            volume += left_max - heights[left]
            left+=1
        else:
            volume += right_max-heights[right]
            right+=1
    return volume