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.
我做题，一般是按照AC率排序选着做的，这道题一不留神，难度居然还是Hard，好吧，确实也难到了我。AC率居然还蛮高，我也是提交了3次之后才AC的。先说说我前两次的错误思路：第一次，我是对每一个点，往两边找最长升序，然后以左右两边的这两个序列的和作为一个坑，用来填雨水。但是针对[5,1,2,1,2,1,2,5]这样的序列，即在区间内部的升降，其实并不影响其盛水，故WA！第二次个人认为也是能完成的，但是需要考虑的情况比较多，比较烦人，不是最合适的方法，方法是从左到右扫描，扫到第一个比当前高的，作为一个区间，接着从区间末开始继续往后扫，以此类推，这方法能解决上面的问题，但是最后一个区间需要单独考虑。
其实是可以这样解决的：先找到最高的那个问题maxhigh，然后分别从两边往这个节点遍历，设置一个次高点temphigh，
如果当前节点比次高点高，则更新次高点，继续；
否则，用次高点减去当前节点，就是我们能盛水的体积。
就是这么简单粗暴，唯一的缺陷就是需要两次扫描，有强迫症的或者追求完美主意的，可以查看下网上的一个方法，是直接从两边开始扫描的，一次搞定。个人感觉代码看上去不够直观。
下面贴一下我自己的代码：
class Solution:
# @param A, a list of integers
# @return an integer
def trap(self, A):
res = 0
if len(A) < 3:
return 0
maxv = 0
maxid = 0
for i in range(len(A)):
if A[i] > maxv:
maxv = A[i]
maxid = i
temphigh = 0
for j in range(maxid):
if A[j] > temphigh:
temphigh = A[j]
else:
res += temphigh - A[j]
temphigh = 0
for j in range(len(A)-1,maxid,-1):
if A[j] > temphigh:
temphigh = A[j]
else:
res += temphigh - A[j]
return res