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 0 11 i = 1 12 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 = RHI 19 else: 20 i += 1 21 22 return sum(height) - S1 23 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 continue 32 else: 33 for j in range(index-1, -1, -1): 34 if height[j] > height[index]: 35 return [j, height[j]] 36 else: 37 continue 38 return [index, height[index]] 39 40