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

The above elevation map 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. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

This problem is very hard. First, you should scan from left to right, keep track current largest height. Second, scan for the right to left, keep tracking the current largest height. Maintain a result list, use ith element in the minimal height of left to right list and right to the left list to minus ith element in height. Return sum of res.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height)<3:
            return 0
        left2right=[0 for _ in range(len(height))]
        right2left=[0 for _ in range(len(height))]
        left2right[0]=height[0]
        right2left[len(height) - 1] = height[len(height) - 1]
        for i in range(1,len(height)):
            if height[i]>left2right[i-1]:
                left2right[i]=height[i]
            else:
                left2right[i]=left2right[i-1]
        for i in range(len(height)-2,-1,-1):
            if height[i]>right2left[i+1]:
                right2left[i]=height[i]
            else:
                right2left[i]=right2left[i+1]
        res=[]
        for i,item in enumerate(height):
            res.append(min(left2right[i],right2left[i])-item)
        return sum(res)