LeetCode 42. Trapping Rain Water

파이썬 알고리즘 인터뷰 문제 8번(리트코드 42번) Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/

나의 풀이(Two Pointers 풀이)

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0

        water = 0
        left, right = 0, len(height) - 1

        while right - left > 1:
            if height[left] < height[right]:
                mid = left + 1
                ground = 0
                while height[left] > height[mid]:
                    ground += height[mid]
                    mid += 1
                water += height[left] * (mid - left - 1) - ground
                left = mid
            else:
                mid = right - 1
                ground = 0
                while height[right] > height[mid]:
                    ground += height[mid]
                    mid -= 1
                water += height[right] * (right - mid - 1) - ground
                right = mid
            
        return water

물을 가두는 양쪽 벽 중 낮은 벽의 높이가 전체 높이가 된다.
따라서 좌우 양 끝에 Two Pointers를 잡은 후,
둘 중 낮은 벽을 더 높은 벽을 만날 때까지 이동시키며 물의 양을 계산하면 된다.
그러면 Two Pointers가 서로 만나게 되며 종료된다.

다른 풀이1(Two Pointers 풀이, 위 풀이랑 거의 같음)

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water = 0

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

다른 풀이2(Stack 풀이)

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

        for curr in range(len(height)):
            while stack and height[stack[-1]] < height[curr]:
                prev = stack.pop()
                if stack:
                    width = curr - stack[-1] -1
                    water += width * (min(height[stack[-1]], height[curr]) - height[prev])


            stack.append(curr)
        
        return water

Two Pointers 풀이가 물을 세로로 더한다면
Stack풀이는 물을 가로로 더한다.

푸는데 한참 걸렸다.
특히 Stack으로 푸는 것은 아주 오래 걸렸음.
꼭 다시 풀어보자.