Trapping Rain Water @ Airbnb

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:

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

Output: 6

题目分析：

这道题乍一看觉得情况太多，如何遍历？破题的关键点在于，我们只focus在计算一格的容水量的情况。

DP解法：

那么每一格trap water的量由什么决定？由这一格 max (height[0]...height[i]) 和 max(height[i+1], ... height[n]) 最小值决定，同时，这一格本身的高度也不能忽视，假如这一格本身的高度远远高于左右两边的最大值，那么这一格就什么水都容不下，所以在计算最高的时候，把本身也得考虑在那。

推导公式：water can trap = min(max(LMax[0..i]), max(i...n)) - height[i]

此时，可以用DP的方式，扫数组两遍，建立起LMax, RMax, 再最后计算出水容量。

DP的本质就是用空间来置换时间，把可重复利用的中间值保存下来，用来计算最后结果。

Time: O(n), Space: O(n)

class Solution {
    int size;
public:
    int trap(vector<int>& height) {
        // LMax, RMax vector
        size = height.size();
        if (size <= 2) return 0;
        vector<int> LMax(size, 0), RMax(size, 0);
        LMax[0] = height[0];
        RMax[size-1] = height[size-1];
        for (int i = 1; i<size; i++)
        {
            LMax[i] = max(LMax[i-1], height[i]);
        }
        for (int i = size-2; i>=0; i--)
        {
            RMax[i] = max(RMax[i+1], height[i]);
        }
        int res = 0;
        for (int i = 1; i<size; i++)
        {
            res += min(LMax[i], RMax[i]) - height[i];
        }
        return res;
    }
};

2 Pointers:

这个想法很有趣，很巧妙，破题的关键点在于，任何一个格子，和DP解法一样，由左边和右边的最大值来决定，而且不论这个最大值的坐标在哪里，这样我们可以一边动态地找最大值，一边来计算water being trapped amount. 

pointer left = 0, right = n-1, 比较height[left] and height[right],  哪边高度小，哪边先挪动，因为小的那个可以当前确定蓄水量。

关键：当前格子的蓄水量由，min(左边最大，右边最大) - 当前节点高度 决定。

此时假如左边挪动，说明左边指针暂时小于右边，此时遇到新的block的情况只能是两种，小于left，大于left，小于left高度的话，可以蓄水，算出来。大于left高度，不能蓄水。更新指针，往前走，继续比较left 和 right 指针高度。

注意点在于，除了使用left, right指针，还得用两个值lmax, rmax来随时更新当前lmax and rmax的情况。因为蓄水量是等于 lmax - height[left] 和 rmax - height[right] 来决定的。

time: O(n)  space: O(1)

class Solution {
    int size;
public:
    int trap(vector<int>& height) {
        size = height.size();
        if (size <= 2) return 0;
        int res = 0, left = 0, right = size-1, lmax = height[0], rmax = height[size-1];
        while (left < right)
        {
            if (height[left] <= height[right])
            {
                left++;
                if (lmax > height[left])
                {
                    res += lmax - height[left];
                }
                else
                {
                    lmax = height[left];
                }
            }
            else
            {
                right--;
                if (rmax > height[right])
                {
                    res += rmax - height[right];
                }
                else
                {
                    rmax = height[right];
                }
            }
        }
        return res;
    }
};