LeetCode - 42. Trapping Rain Water

Hard

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.

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      

Soultion 1:  暴力破解

1. 循环设定当前位置

2. 向左取最大值

3. 向右取最大值

4. 当左右最大值中的最小值大于当前位置值时，最小值减去当前位置值就是可存的雨量。

时间复杂度：O(

)。

空间复杂度：O(1)。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        for cur in range(1, len(height)-1):
            left_max = max(height[:cur])
            right_max = max(height[cur+1:])
            if min(left_max, right_max) > height[cur]:
                ans += min(left_max, right_max) - height[cur] 
        return ans
           

Time Submitted	Status	Runtime	Memory	Language
2 hours ago	Accepted	2240 ms	14.6 MB	python3

 Solution 2： Dynamic Programming

1. 分别新建左右两个列表，与原列表一致。注意不要用left = height，这个还是指向同一个对象。

2. 从左向右遍历，取左边最大值并存入左列表中

3. 从右向左遍历，取右边最大值并存入右列表中

4. 比较同一位置左右列表的值，取最小值并减去原列表该位置的值，即为当前位置的雨滴存量。

时间复杂度：O(n)。

空间复杂度：O(n)。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height or len(height) < 3:
            return 0
        ans = 0
        size = len(height)
        left = height[:]
        right = height[:]

        for i in range(1, size):
            left[i] = max(left[i-1],left[i])
        for i in range(size-2, -1, -1):
            right[i] = max(right[i], right[i+1])
        for i in range(size):
            ans += min(left[i], right[i]) - height[i]
        
        return ans
           

Status	Runtime	Memory	Language
a few seconds ago	Accepted	56 ms	14.5 MB	python3

Solution 3: Stack

1. 建立一个空栈，往里面存储位置以及该位置的值

2. 如果列表当前的值大于栈顶元素，把栈顶元素推出。然后查看栈中是否有元素，有则算作左边，然后计算可存储的雨滴。继续循环，直到栈中的值比当前元素大或为空，然后把当前值插入栈中

3. 循环直到列表结束。

时间复杂度：O(n)。

空间复杂度：O(n)。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height or len(height) < 3:
            return 0
        ans = 0
        minus = 0
        stack = []
        for cur in range(len(height)):
            # if current height is greater than top, pop out
            while stack and height[cur] >= stack[-1][1]:
                    popped = stack.pop()
                    # to check if have left, if yes, calculate the rain drop
                    if stack:
                        left = stack[-1]
                        ans += (cur - left[0] -1) * min(left[1]-popped[1], height[cur]-popped[1])
            stack.append([cur, height[cur]])

        return ans
        
           

Status	Runtime	Memory	Language
a few seconds ago	Accepted	52 ms	14.6 MB	python3

Solution 4: Two pointers 

 利用左右指针来遍历

1. 设置左右两个指针l = 0, r = len(height) -1，并设置l_max和r_max为0。

2.当左指针位置小于右指针位置，

2.1 如果左指针的值小于右指针的值，那么相当于桶的右墙高度已经确定，那么这时就需要查看，左边的墙是否有？有的话为多少。这个时候就需要比较左指针的值与左边最大值的大小。如果左指针的值小于左最大值，那么左最大值就是该位置的左墙，那么无论右边多少，可存储的雨滴量为左最大值减去当前值。如果左指针的值大于左最大值，那么左墙不存在，更新左最大值。

2.2 右边同理

当左指针比右边小时，l_max 也比 r_max。

3. 最后返回所有的雨滴总量。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height or len(height) < 3:
            return 0
        ans = 0
        l = 0
        r = len(height)-1
        l_max = 0
        r_max = 0
        
        while(l<r):
            if height[l] <= height[r]:
                if height[l] < l_max:
                    ans += l_max - height[l]
                else:
                    l_max = height[l]
                l += 1
            else:
                if height[r] < r_max:
                    ans += r_max - height[r]
                else:
                    r_max = height[r]
                r -= 1
        
        return ans
           

Success

Runtime: 40 ms, faster than 99.20% of Python3 online submissions for Trapping Rain Water.

Memory Usage: 14.5 MB, less than 6.98% of Python3 online submissions for Trapping Rain Water.

Time Submitted	Status	Runtime	Memory	Language
a few seconds ago	Accepted	40 ms	14.5 MB	python3