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