042._trapping_rain_water.md

###42. Trapping Rain Water

题目: https://leetcode.com/problems/trapping-rain-water/

难度: Hard

思路：

题目有几个特性可用，bar width = 1,然后第一个和最后一个是不能trap water，其次中间的部分能trap多少水是看左右高度差教低的那个 - 本身的高度，所以就是本身的比较高就不能trap water了，这种情况取0.

AC代码：

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height: return 0
        n = len(height)

        rightH = [0 for i in range(n)]
        rightH[n-1] = height[n-1]

        for i in range(n-2,0,-1):
        	rightH[i] = max(rightH[i+1],height[i+1])
        # print rightH


        leftH = [0 for i in range(n)]
        leftH[0] = height[0]
        for i in range(1,n):
        	leftH[i] = max(leftH[i-1],height[i-1])
        # print leftH

        water = 0
        for i in range(1,n-1):
        	water += max(0, min(leftH[i],rightH[i]) - height[i])
        	print water
        return water