class Solution:
def calLeft(self,height,rightval,left,right):
if left>=right:
return 0
sums = 0
maxindex=0
maxval=-1
for i in range(left,right):
cur = height[i]
if cur>maxval:
maxval=cur
maxindex=i
waterlevel = min(maxval,rightval)
for i in range(maxindex+1,right):
sums += max(0,waterlevel-height[i])
sums += self.calLeft(height,waterlevel,0,maxindex)
return sums
def calRight(self,height,leftval,left,right):
if left>=right:
return 0
sums = 0
maxindex = 0
maxval = -1
for i in range(right,left,-1):
cur = height[i]
if cur>maxval:
maxval=cur
maxindex = i
waterlevel = min(maxval,leftval)
for i in range(left+1,maxindex):
sums += max(0,waterlevel-height[i])
sums +=self.calRight(height,waterlevel,maxindex,len(height)-1)
return sums def trap(self, height: 'List[int]') -> int:
maxindex = 0
maxval = -1
sums = 0
for i in range(len(height)):
curval = height[i]
if curval > maxval:
maxval = curval
maxindex = i
sums += self.calLeft(height,maxval,0,maxindex)
sums += self.calRight(height,maxval,maxindex,len(height)-1)
return sums
这道题的主要思想是搜索，先找到最大的值maxval，对应的索引maxindex，然后向左右两个方向分别搜索。记height的长度为length。
左侧的部分[0,maxindex)，从小到大寻找当前区间的最大值leftmaxval，对应的索引leftmaxindex，然后从计算(leftmax,maxindex)之间的区域。
用递归的方式，继续计算[0,leftmaxindex)，一直到这个区间长度为0，不再进行递归。
同理，右侧部分(maxindex,length]，从大到小寻找最大值rightmaxval，对应的索引rightmaxindex，然后计算(midindex,rightmaxindex)之间的区域。
用递归的方式，继续计算(rightmaxindex,length]，一直到这个区间的长度为0，不再进行递归。
在主函数中，找到全局的（第一个出现的，也可以是任意一个）最大值，然后分别调用左右两侧的递归方法。
这里有个小技巧（贪心思想），就是左侧区间找最靠左的最大值，右侧区找最靠右的最大值。这样能尽可能扩大每次搜索所确定的区域，使得在每次搜索到多个相等的最大值时，可以减少递归次数。
本题还有其他的解决方案，使用非递归的方式效率更高。