[Python] Leet Code 42. Trapping Rain Water

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

투 포인터를 최대 값으로 이동

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

        left, right = 0, len(height)-1
        left_max, right_max = 0, 0
        volume = 0

        while left < right:
            left_max, right_max = max(left_max, height[left]), max(right_max, height[right])
            if height[left] < height[right]:
                volume += (left_max - height[left])
                left += 1
            else:
                volume += (right_max - height[right])
                right -= 1


        return volume

이 문제에서 배워야할 포인트

• 양 끝에서 투 포인터 시작, 최대 높이로 모인다
• 최대 높이는 전체 부피에 영향을 끼치지 않고, 그저 장벽 역할을 한다
• 양 옆으로 훓으며 세로 부피만큼 더해준다

스택 쌓기

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

        stack = []
        volume = 0

        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()

                if not len(stack):
                    break

                distance = i - stack[-1] -1
                waters = min(height[i], height[stack[-1]]) - height[top]

                print("i:{}, dist:{}, waters:{}".format(i, distance, waters))
                volume += distance * waters

            stack.append(i)

        return volume

i:3, dist:1, waters:1
i:6, dist:1, waters:1
i:7, dist:2, waters:0
i:7, dist:3, waters:1
i:10, dist:1, waters:1

이 문제에서 배워야할 포인트

• 왼쪽에서 오른쪽으로 훓으며 스택에 index 추가
• 스택 top의 높이가 현재 높이보다 작을 때, 스택을 비워준다
• 스택을 비울 때, 가로 부피만큼 volume에 가산해준다