# 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 can trap after raining.

### Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

### Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

### Constraints:
`n == height.length`
`1 <= n <= 2 * 104`
`0 <= height[i] <= 105`

## 解題
每格裡面最多能夠儲存 min(向左尋找最高的牆, 向右尋找最高的牆)的水量，計算出每格可儲存水量後加總即是答案

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        
        // calculate the highest wall between index i to n-1
        int max_r[height.size()];
        max_r[height.size()-1] = height[height.size()-1];
        for(int i=height.size()-2; i>=0; i--) {
            max_r[i] = max(max_r[i+1], height[i]);
        }
        
        // the highest wall to the left can be calculate will traveling
        int max_l = 0;
        for(int i=0; i<height.size(); i++) {
            max_l = max(max_l, height[i]);
            int h = min(max_l, max_r[i]) - height[i];
            ans += h;
        }
        return ans;
    }
};