# 42 - Trapping Rain Water

解法一 - DP

這個解法挺 elegant 的，個人頗推。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftMax(n), rightMax(n);

        int maxH = -1;
        for(int i=0; i<n; i++) {
            maxH = max(maxH, height[i]);
            leftMax[i] = maxH;
        }

        maxH = -1;
        for(int i=n-1; i>=0; i--) {
            maxH = max(maxH, height[i]);
            rightMax[i] = maxH;
        }

        int res = 0;
        for(int i=0; i<n; i++) {
            int trap = min(leftMax[i], rightMax[i]) - height[i];
            if(trap > 0) res += trap;
        }

        return res;
    }
};

解法二 -

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