Leetcode** 42. Trapping Rain Water

Example 1:
 

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. 
In this case, 6 units of rain water (blue section) are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height: return 0
        n = len(height)
        max_left = [0]*n
        max_right = [0]*n
        for i, h in enumerate(height):
            max_left[i] = max(max_left[i-1], height[i])
        max_right[-1] = height[-1]
        i = n - 2
        while i >= 0:
            max_right[i] = max(max_right[i+1], height[i])
            i -= 1
        res = 0
        for i, h in enumerate(height):
            res += max(0, (min(max_left[i], max_right[i]) - h))
        return res