LeetCode 42 Trapping Rain Water

Posted on | In | 阅读

2-SUM 同类型题目， 与LeetCode11思想相似

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.

img
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 Marcosfor contributing this image!

  • 这题会卡时间限制，要求使用O(n)的方法来解决这个问题；
  • 实际上只需要计算每个格子左右的高度最大值中取较小的那个与当前的高度取正差值即可；
  • 优化：可以仅遍历一次就完成计算，即设置左指针与右指针，并且记录左指针左边的最大值以及右指针右边的最大值，每次比较两个最大值，如果左最大值小于右最大值，那么右边不会对左指针指的位置产生限制，直接用左最大值计算即可，右边同理；

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        length = len(height)
        if height == None or length == 0:
            return 0
        
        l = 0
        r = length - 1
        result = 0
        
        maxL = maxR = 0
        
        while l <= r:
            maxL = max(height[l], maxL)
            maxR = max(height[r], maxR)
            
            if maxL < maxR:
                result += maxL - height[l]
                l += 1
            else:
                result += maxR - height[r]
                r -= 1
        return result