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

가장 높은 위치에 도달할 때 가지 두 포인터가 -> <-방향으로 서로 이동함

스택 풀이

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]
               
               volume += distance * waters
           stack.append(i)
       return volume

• stack[-1] : 맨 위에있는 것을 꺼낸다

  스택의 높낮이가 바뀌는 부분을 기준으로 물 높이 volume을 채움