LEETCODE - Trapping Rain Water

class Solution:
    def trap_two_point(self, height: list[int]) -> int:
        if not height:
            return 0

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

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

            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return volume
    def trap_stack(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]

                volume += distance * waters
            stack.append(i)

        return volume
    # stack =[0,2,3] top = 4, stack[-1] = 3 i = 5, distance = 1
    # stack = [0,2] top = 3 stack[-1] = 2 i = 6 distance = 3