42. Trapping Rain Water

Option 1: it is easy to start from brute force to DP solution. Key point is to find max height at left side and right side of each index i

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        
        if n == 0:
            return 0
        
        left_max = [0] * n
        left_max[0] = height[0]
        for i in range(n):
            left_max[i] = max(left_max[i-1], height[i])
        
        right_max = [0] * n
        right_max[-1] = height[-1]
        for i in range(n-2, -1, -1):
            right_max[i] = max(right_max[i+1], height[i])
        
        total = 0
        for i in range(n):
            total += min(left_max[i], right_max[i]) - height[i]
        return total

Option 2: 递减stack

when to pop?

popping when the height contributed by it is determined => there is an element higher than it at its left side (eg, next top in stack) and there is an element higher than it at its right side (cur index under processing)
what if hight of cur bar is equal to top of stack? we can either kick out the top or append cur, result is correct as long as we process this situation in a consistent manner

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        stack = []
        total = 0
        for i in range(n):
            while stack and height[i] > height[stack[-1]]:
                pop = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                total += (min(height[i], height[left]) - height[pop]) * (i - left - 1)
            stack.append(i)
        return total

Option 3: 2 points

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        total = 0
        while left < right:
            if height[left] >= height[right]: # contirbution of right is determined
                total += max(0, right_max - height[right])
                right_max = max(right_max, height[right])
                right -= 1
            else: # contirbution of left is determined
                total += max(0, left_max - height[left])
                left_max = max(left_max, height[left])
                left += 1
        return total

42. Trapping Rain Water - cocoder39/coco39_LC GitHub Wiki