Leetcode 42. Trapping Rain Water

Trapping Rain Water :

給定 n 個非負整數，每個條的寬度為 1 的柱狀圖，計算下雨後它可以捕獲多少水。

時間複雜度: O(n)

空間複雜度: O(n)

Python

解法一 : 雙指針

在左右兩端分別設置指針left, right，left_max 就是指針left 左邊最高的線，height[left] < height[right]，左邊已經走過的位置都小於 height[right]，表示左指針指向的數字< 右指針指向的數字，所以要操作左指針，現在left指針位置的左右兩邊桶的短板，一定存在於左邊。

右指針同例

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height : return 0
        left_max=right_max=result=0
        left=0
        right=len(height)-1
        
        while left<right:
            if height[left]<height[right]:       #左指針
                if height[left]<left_max:        #小於max max減掉陣列值
                    result+=left_max-height[left]
                else:                            #大於max max等於陣列值
                    left_max=height[left]
                left+=1                          #左指針右移
            else:
                if height[right]<right_max:      #右指針
                    result+=right_max-height[right]
                else:
                    right_max=height[right]
                right-=1
        return result

解法二 :

（1）從左向右進行掃描，獲取每個位置的左邊最高的邊。
（2）從右向左進行掃描，獲取每個位置的右邊最高的邊。
（3）再遍歷一邊，計算出每個位置的容量，累加之後得到結果。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height : return 0
        n,result=len(height),0
        left_max,right_max=[0]*n,[0]*n
        
        left_max[0]=height[0]
        for i in range(1,n):         #左向右，左邊最高的邊
            left_max[i]=max(height[i],left_max[i-1])
        
        right_max[n-1]=height[n-1]
        for i in range(n-2,-1,-1):   #右向左，右邊最高的邊
            right_max[i]=max(height[i],right_max[i+1])
        
        for i in range(1,n-1):
            result+=min(left_max[i],right_max[i])-height[i]
        return result

C++

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1, level = 0, res = 0;
        while (l < r) {
            int lower = height[(height[l] < height[r]) ? l++ : r--];
            level = max(level, lower);
            res += level - lower;
        }
        return res;
    }
};