【Leetcode】【python】Trapping Rain Water 接雨水

题目大意

给定数组A，A[i]表示第i个位置的高度，求可以盛放雨水的容量。

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

纯思路

网上有多种思路，不尽相同但是思路类似，这里贴一个供参考。

参考：http://www.cnblogs.com/zuoyuan/p/3781453.html

开辟一个数组leftmosthigh，leftmosthigh[i]为A[i]之前的最高的bar值，然后从后面开始遍历，用rightmax来记录从后向前遍历遇到的最大bar值，那么min(leftmosthigh[i], rightmax)-A[i]就是在第i个bar可以储存的水量。例如当i=9时，此时leftmosthigh[9]=3,而rightmax=2，则储水量为2-1=1，依次类推即可。这种方法还是很巧妙的。时间复杂度为O(N)。

栈

https://blog.csdn.net/sunnyyoona/article/details/18557669
代码略

代码

纯思路

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left_temp_max = [0 for i in range(len(height))]  # 每个位置的左边最高值
        left_max = 0
        right_max = 0
        for i in range(len(height)):
            if height[i] > left_max: 
                left_max = height[i]
            left_temp_max[i] = left_max
            
        total = 0
        for i in range(len(height)-1, -1, -1):
            if height[i] > right_max: 
                right_max = height[i]
            if min(right_max, left_temp_max[i]) > height[i]:  # 主要判断
                total += min(right_max, left_temp_max[i]) - height[i]
        return total

总结