> For the complete documentation index, see [llms.txt](https://zhongwen.gitbook.io/leetcode-report/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongwen.gitbook.io/leetcode-report/hard/42.-trapping-rain-water.md).

# 42. Trapping Rain Water

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.

![](https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png)\
The above elevation map is represented by array \[0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. **Thanks Marcos** for contributing this image!

**Example:**

```
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
```

#### 解题要点：

用Dynamic Programming，先从左至右搜索一遍，记录最大值，再从右至左搜索一遍，同样记录最大值。最后遍历的时候取min(left\[i], right\[i])，再减去height\[i]，记录为结果。

```python
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if height == None or len(height) == 0:
            return 0
        leftDP = [0] * len(height)
        rightDP = [0] * len(height)
        leftDP[0] = height[0]
        rightDP[-1] = height[-1]
        for i in range(1, len(height)):
            leftDP[i] = max(leftDP[i-1], height[i])
        for j in range(len(height)-2, -1, -1):
            rightDP[j] = max(rightDP[j+1], height[j])
        res = 0
        for k in range(len(height)):
            res += min(leftDP[k], rightDP[k]) - height[k]
        return res
```