42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

My Answer 1: Wrong Answer (50 / 320 test cases passed.)

class Solution:
    def trap(self, height: List[int]) -> int:
        result = 0
        
        left = 0
        right = 0
        
        temp = 0
        i = 0
        while i < len(height):
            if height[i] != 0 and left == 0:
                left = height[i]
                for j in range(i+1, len(height)):
                    if left <= height[j]:
                        result += temp
                        left = 0
                        i = j-1
                        break
                    # 물이 담길 공간이 없으므로
                    if j == len(height)-1:
                        temp = 0
                        break
                    temp += left - height[j]
                    
            i += 1
        
        return result

left 값 보다 큰 값이 나오면 물이 담길 수 있으니까 그때의 넓이들을 더해줌
하지만 [4,2,3] 같은 경우는 고려하지 못해서 right 값도 잡아주려고 했는데.. 뭔가 잘 안됨

Solution 1: Runtime: 56 ms - 61.58% / Memory Usage: 14.8 MB - 88.49%

class Solution:
    def trap(self, height: List[int]) -> int:
        
        if len(height)<= 2:
            return 0
        
        ans = 0
        
        #using two pointers i and j on indices 1 and n-1
        i = 1
        j = len(height) - 1
        
        #initialising leftmax to the leftmost bar and rightmax to the rightmost bar
        lmax = height[0]
        rmax = height[-1]
        
        while i <=j:
            # check lmax and rmax for current i, j positions
            if height[i] > lmax:
                lmax = height[i]
            if height[j] > rmax:
                rmax = height[j]
            
            #fill water upto lmax level for index i and move i to the right
            if lmax <= rmax:
                ans += lmax - height[i]
                i += 1
				
            #fill water upto rmax level for index j and move j to the left
            else:
                ans += rmax - height[j]
                j -= 1
                
        return ans

i 는 1부터, j 는 맨 끝부터 잡아두고 lmax 는 첫번째 값을, rmax 는 맨 마지막 값으로 설정

반복문을 돌려서 height 값이 lmax, rmax 값 보다 크면 각각 update 를 해줌
lmax 가 rmax 보다 작으면 lmax ~ height 의 넓이를 더해주고
반대면 rmax ~ height 의 넓이를 더해준다.

Time complexity O(n)
Space complexity O(1)

그냥 냅다 외워!!!