## 題解


class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left_max = right_max = left = waters = 0
        right = n - 1

        while left <= right: # 小於等於，因為要讓他算完
            if left_max < right_max:
                if height[left] < left_max: # 如果當前的數字小於左邊最大才需要計算水位
                    waters += left_max - height[left]
                else: # 大於就更新左邊最大水位
                    left_max = height[left]
                left += 1
            else: # 同上
                if height[right] < right_max:
                    waters += right_max - height[right]
                else:
                    right_max = height[right]
                right -= 1
        
        return waters

2023.10.27 AC

class Solution:
    def trap(self, height: List[int]) -> int:
        # Time complexity: O(n)
        # Space complexity: O(1)
        n = len(height)
        left = 0
        right = n - 1
        left_max = right_max = 0
        water = 0
        # 從最左邊和最右邊開始 (計算左邊所有容器和右邊所有容器內的水)
        while left <= right:
            if left_max <= right_max: # 比較小的先走
                if height[left] < left_max: # 比較 left_max 是否比現在的大
                    water += left_max - height[left] # 現在的比較小就計算差值
                else: # height[left] >= left_max 視為一個容器
                    left_max = height[left] # 比較大就代表到達一個容器的邊界，更新最左邊的容器邊界
                left += 1
            else:
                if height[right] < right_max: # 比較 right_max 是否比現在的大
                    water += right_max - height[right] # 現在的比較小就計算差值
                else: # height[right] >= right_max 視為一個容器
                    right_max = height[right] # 比較大就代表到達一個容器的邊界，更新最右邊的容器邊界
                right -= 1
        return water