【leetcode】Trapping Rain Water

浏览数：46 / 时间：2015年06月11日

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

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

【leetcode】Trapping Rain Water