# 【LeetCode】 42. Trapping Rain Water

## Description
> 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:

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

## Solution

* `該行可以容納的水量` = `左側最高高度`與`右側最高高度` 取較**小**的值再減掉`自身高度`。(不能小於零)
* MyWater = min(LeftMaxHeight,RightMaxHeight) - MyHeight;
* 算左邊最高高度和右邊最高高度可以使用動態規劃實作與加速。以左邊為例，`左邊最高高度` = `我左邊那一格高度`與`我左邊那個的左邊最高高度`取較**大**值。
* LeftMaxHeight[i] = max(LeftMaxHeight[i-1],height[i-1]);
* 速度應該還能加快，但目前沒想到什麼好作法。
* 目前複雜度是O(3n) = O(n)了，應該是細節要調整。

### Code

class Solution {
public:
    
    int *tableL,*tableR;
    int s;
    int FindLeftMax(vector<int>& height,int location)
    {
        if(location == 0)   return height[0];
        if(tableL[location]==-1)   tableL[location] = max(height[location-1],FindLeftMax(height,location-1));
        return tableL[location];
    }
    int FindRightMax(vector<int>& height,int location)
    {
        if(location == s-1) return height[s-1];
        if(tableR[location]==-1)   tableR[location] = max(height[location+1],FindRightMax(height,location+1));
        return tableR[location];
    }
    
    int trap(vector<int>& height) {
        int count=0;
        s = height.size();
        tableL = new int[s];
        tableR = new int[s];
        
        for(int i=0;i<s;i++)
            tableL[i] = tableR[i] = -1;
        
        if(s!=0)
            for(int i=1;i<s-1;i++)
            {
                count += max(0,min(FindLeftMax(height,i),FindRightMax(height,i))-height[i]);
            }
        return count;
    }
};

###### tags: `LeetCode` `C++`