Trapping Rain Water

# 기존 풀이

# 빗물이 잠길 때 마다 잠긴 value 를 더해주면
# 최종적으로 전체 빗물을 리턴할 수 있겠다.

# 어떻게 잠긴 빗물을 계산할 수 있을까?

# 입력 = [0,1,0,2,1,0,1,3,2,1,2,1]
# 빗물 = [0,0,1,0,1,2,1,0,0,1,0,0]
# [0,0,(2-1),0,(2-1),(2-1),(2-1),0,0,(2-1),0,0]

# 좌측 0 번째 우측 마지막 번째는 빗물 계산 안함
# 투포인터 사용하여 왼쪽, 오른쪽 각각 index 를 이동시킨다고 가정했을 때
# 2 는 index 가 이동하면서 발견한 최대 높이
# 1 은 현재 높이
# 최대높이 - 현재높이 만큼 전체 빗물에 추가

# input [2,0,2] 일 때 실패

# 문제점

# 최대높이가 중간에 없으면 포인터가 이동하지 않음

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

        if len(height) < 2:
            return 0

        total_max_height = max(height)
        total_water = 0

        left_index = 0
        right_index = len(height)-1

        left_max_height = height[left_index]
        right_max_height = height[right_index]

        while left_max_height < total_max_height:

            left_max_height = max(height[left_index], left_max_height)

            if left_max_height > height[left_index]:

                total_water += left_max_height - height[left_index]

            left_index += 1

        while right_max_height < total_max_height:

            right_max_height = max(height[right_index], right_max_height)

            if right_max_height > height[right_index]:

                total_water += right_max_height - height[right_index]

            right_index -= 1

        return total_water

# 최종 풀이

# 일단 무조건 왼쪽 포인터, 오른쪽 포인터가 최대한 이동할 수 있도록 반복문을 지정

# 하지만 왼쪽 포인터, 오른쪽 포인터 모두 최대높이에 도달하면 멈춰야 함

# 왼쪽, 오른쪽 둘중 하나의 높이가 다른 쪽 보다 낮으면 이동하고 높으면 정지

# 최대 높이가 현재높이보다 크면 최대높이- 현재높이 만큼 물에 추가

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

        if len(height) < 2:
            return 0

        total_max_height = max(height)
        total_water = 0

        left_index = 0
        right_index = len(height)-1

        left_max_height = height[left_index]
        right_max_height = height[right_index]

        while right_index > left_index:

            right_max_height = max(height[right_index], right_max_height)
            left_max_height = max(height[left_index], left_max_height)

            if(right_max_height <= left_max_height):

                if(right_max_height > height[right_index]):
                    total_water += right_max_height - height[right_index]

                right_index -= 1

            else:

                if(left_max_height > height[left_index]):
                    total_water += left_max_height - height[left_index]

                left_index += 1

        return total_water