from typing import *


class Solution:
    def trap(self, height: List[int]) -> int:
        # trapSide的参数中height最右侧一定是最高的
        def trapSide(height: List[int]):
            if not height or len(height) < 3:
                return 0
            max_height, max_index = 0, 0
            for i in range(len(height) - 1):
                if height[i] >= max_height:
                    max_height, max_index = height[i], i

            sum_water = 0
            for i in range(max_index, len(height) - 1):
                sum_water += max_height - height[i]
            sum_water += trapSide(height[:max_index + 1])
            return sum_water

        if len(height) < 3:
            return 0

        sum_water, max_height, max_index = 0, 0, 0
        for i in range(len(height)):
            if height[i] >= max_height:
                max_height, max_index = height[i], i

        sum_water += trapSide(height[:max_index + 1])
        sum_water += trapSide(height[max_index:][::-1])
        return sum_water


if __name__=='__main__':
    s = Solution()
    print(s.trap([0,1,0,2,1,0,1,3,2,1,2,1]))
