042._trapping_rain_water.md

42. Trapping Rain Water

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

难度: Hard

思路：

题目有几个特性可用，bar width = 1,然后第一个和最后一个是不能trap water，其次中间的部分能trap多少水是看左右高度差较低的那个 - 本身的高度

The basic idea is that we set two pointers l and r to the left and right end of height. Then we get the minimum height (min_height) of these pointers (similar to Container with Most Water due to the Leaking Bucket Effect) since the level of the water cannot be higher than it. Then we move the two pointers towards the center. If the coming level is less than min_height, then it will hold some water. Fill the water until we meet some “barrier” (with height larger than min_height) and update l and r to repeat this process in a new interval.

AC代码：

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l, r, water, min_height = 0, len(height) - 1, 0, 0
        while l < r:
            min_height = min(height[l], height[r])
            while l < r and height[l] <= min_height:
                water += min_height - height[l] 
                l += 1
            while l < r and height[r] <= min_height:
                water += min_height - height[r]
                r -= 1
        return water