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.

思路：显然index = 0 and size - 1 这两个位置不会存水。只需要考察这中间的位置。如果一个位置 index (e.g. 2), 左边和右边都有比它大的数，index上面才可能有水。写一个subroutine来找左（右）边第一个高于index的位置，并记录下这个高度为 LH, RH。存水会使LHI, RHI之间的所有位置高度都变成min(RH, LH)。然后我们跳到 RHI这个位置接着再找就可以。

1 class Solution(object): 2     def trap(self, height): 3         """ 4         :type height: List[int] 5         :rtype: int 6         """ 7         size = len(height) 8         S1 = sum(height) 9         if size <= 2:10             return 011         i = 112         while i <= size -1:13             [RHI, RH] = self.firstHigher(height, i, True)14             [LHI, LH] = self.firstHigher(height, i,False)15             if RHI>i and RHI > LHI+1:16                 for k in range(LHI+1, RHI):17                     height[k] = min(RH, LH)18                 i = RHI19             else:20                 i += 121             22         return sum(height) - S123              24     def firstHigher(self, height, index, right):25         size = len(height)26         if right == True:27             for j in range(index+1,size):28                 if height[j] > height[index]:29                     return [j, height[j]]30                 else:31                     continue32         else:33             for j in range(index-1, -1, -1):34                 if height[j] > height[index]:35                     return [j, height[j]]36                 else:37                     continue38         return [index, height[index]]39     40