# Leetcode 42. Trapping Rain Water
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/trapping-rain-water/ 。

想法 :

找到每一個位置的左方最大與右方最大，它的蓄水高度就是兩者取小減掉自己本身的高度。
所以先找所有位置的左方最大，並找右方最大。
接著再跑一次總合即為答案。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int trap(vector<int>& height) {
        int l=height.size(), sum=0, left_max[20010]={0}, right_max[20010]={0};
        
        left_max[0]=height[0];
        for(int i=1 ; i<l ; i++){
            left_max[i]=max(left_max[i-1], height[i]);
        }
        
        right_max[l-1]=height[l-1];
        for(int i=l-2 ; i>=0 ; i--){
            right_max[i]=max(right_max[i+1], height[i]);
        }
        
        for(int i=0 ; i<l ; i++){
            sum+=(min(left_max[i], right_max[i]) - height[i]);
        }
        
        return sum;
    }
};