[Leetcode] 42. Trapping Rain Water

7909 ワード

「Pythonアルゴリズムインタビュー」という本でコードテストを勉強するとき、解答を見ても理解できないところがあるので、先に記録して、後で理解を残しておきましょう.
  • Trapping Rain Water
    高さを入力し、雨上がりにどれだけの水が溜まるかを計算します.
  • 最初の方法ポインタを最大値に移動


    この方法は別のブログ記事で理解された.
    class Solution:
        def trap(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

    第2の方法スタッキング


    この方法は他のブログの文章を見ても読めません...
    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]]:  # 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