숫자 배열의 증가/감소 패턴을 인지하는 코드 생성
https://leetcode.com/problems/trapping-rain-water/

22-05-30

fail..
스택쌓기로 풀었는데, 잘 안됨..

Next what to do
1. 투 포인터 사용
'''
So, we can set 2 pointers left_max,right_max and check which side is greater,if one side is greater iterate on other side because at the min side the water will be filled at its limit. and iterate till pointer is lower than the other one.
'''
2. 1번 성공 시, 스택쌓기 재도전

24-09-10

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        if len(height) < 2 or min(height) == max(height):
            return 0

        water_left, water_right = [], []
        top_height_left, top_height_right = height[0], height[-1]

        for i in range(1,len(height)):

            left_gap,right_gap = top_height_left-height[i],top_height_right-height[len(height)-i]
            
            water_left.append(max(left_gap, 0))
            water_right.append(max(right_gap,0))

            top_height_left, top_height_right = max(top_height_left, height[i]), max(top_height_right, height[len(height)-i])

        water = 0
        for i in range(len(height)-1):
            water += min(water_left[i], water_right[len(height)-1-i-1])

        return water

1. 왼쪽으로 슬라이딩 하면서 가장 높은 벽과 현재 벽의 차이 구함.
2. 오른쪽으로 슬라이딩 하면서 1번과 유사하게 구함.
3. 1번과 2번의 산출된 값 중에 작은 값이 water 높이임.

Next what to do
좌우 포인터가 가운데로 점점 이동하여 만난다는 방향으로 코드 작성하기