#42 Trapping Rain Water——Top 100 Liked Questions

心已赠人 2022-01-31 14:57 84阅读 0赞

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.

![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

> """
> 
> 第一次：参考答案，依次遍历，对每个元素，分别找到左右两边最大的值，取两者中的较小值与当前元素值作差，累加到结果res上，时间超时
> 
> """
> 
>     class Solution(object):
>         def trap(self, height):
>             """
>             :type height: List[int]
>             :rtype: int
>             """
>             res = 0
>             n = len(height)
>             for i in range(n):
>                 max_left = 0
>                 max_right = 0
>                 for p in range(0, i + 1):
>                     max_left = max(max_left, height[p])
>                 
>                 for q in range(i, n):
>                     max_right = max(max_right, height[q])
>                                
>                 res += (min(max_left, max_right) - height[i])
>     
>             return res
> 
> """
> 
> Time Limit Exceeded
> 
> """

> """
> 
> 第二次：每次都要找某个元素左右两边的最大值，可采用动态规划
> 
> """
> 
>     class Solution(object):
>         def trap(self, height):
>             """
>             :type height: List[int]
>             :rtype: int
>             """
>             if not height:
>                 return 0
>             res = 0
>             n = len(height)
>             max_left = [0] * n
>             max_right = [0] * n
>             max_right[-1] = height[-1]
>             for i in range(n):
>                 max_left[i] = max(height[i], max_left[i - 1])
>             for j in range(n - 2, -1, -1):
>                 max_right[j] = max(height[j], max_right[j + 1])
>             print(max_left)
>             print(max_right)
>             print(height)
>             for k in range(n):
>                 res += (min(max_left[k], max_right[k]) - height[k])
>             return res
> 
> """
> 
> Runtime: 60 ms, faster than 25.75% of Python online submissions for Trapping Rain Water.
> 
> Memory Usage: 12.6 MB, less than 9.56% of Python online submissions for Trapping Rain Water.
> 
> """

[rainwatertrap.png]: https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png