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.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

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!

题意分析：

　　给定一个非负整数的list，每一个元素代表如图中柱状图的纵坐标。结合图中来看，黑色的是给定的list，让你求出这些黑色柱体围起来能够盛的水量是多少，也就是图中蓝色柱体的面积（每个柱体宽都是1）。

解答：

　　本题和11. Container With Most Water有些类似，那道题求的是两个坐标之间能够盛的最大水量，本题是所有坐标中能够盛下的水量。考虑到每个坐标宽度都是1，所以我们把问题简化为求每个坐标上面能够盛的水量。

　　那么单个坐标的水量怎么求呢？我们假设i为当前需要求的坐标，如果i左侧比i高且是最高的设为left_max，同时能够保证i右侧有比left_max高的坐标，那么i能够盛的水量就是left_max减去i。基于这样一种思路，我们依然可以用双指针的方式去解。

AC代码：

class Solution(object):

    def trap(self, height):

        ret_num = 0

        left, right, left_max, right_max = 0, len(height) - 1, 0, 0

        while left <= right:

            if height[left] < height[right]:

                if height[left] >= left_max:

                    left_max = height[left]

                else:

                    ret_num += left_max - height[left]

                left += 1

            else:

                if height[right] >= right_max:

                    right_max = height[right]

                else:

                    ret_num += right_max - height[right]

                right -= 1

        return ret_num