42. Trapping Rain Water

// Double points, or we can use DP (2 vectors to maintain left-max and right-max of each point.)
class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0, i = 0, j = height.size()-1, lh = 0, rh = 0;
        while (i <= j) {
            if (height[i] >= lh) { lh = height[i++]; continue; }
            if (height[j] >= rh) { rh = height[j--]; continue; }
            
            if (lh <= rh)
                res += lh - height[i++];
            else
                res += rh - height[j--];
        }
        return res;
    }
};