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.

Analysis:
1.直接的想法(not AC)
找到一个“V”型区间，区间中间就是每个区间可以接的水。

提交后，发现有case错误，原来这种解法相当于是贪心，没办法对求对全局的case，[5,2,1,2,1,5]。

2.直接且正确的解法
对于每个元素，向左边的序列找到最高点max_left，向右边的序列找到最高点max_right，则当前元素可以保存的水就是min(max_left, max_right) - height[i]。

注意：在左(右)序列求最高点，要包含当前元素。
时间复杂度O(N^2)

3.动态规划解法
解法2中求左(右)序列中最高点，每次都需要遍历，这里可以优化，我们可以把先前的结果保存，具体是
用max_left[i]表示下标i左边序列的最高点，则max_left[i + 1] = max(max_left[i], height[i + 1])，同理右序列相同。

Solution1:
not AC，超时。

int trap(vector<int>& height) {
    int len = height.size();
    int ret = 0;
    for (int i = 1; i < len - 1; i ++) {
        int max_left = 0, max_right = 0;
        for (int j = i; j >= 0; j --)
            max_left = max(max_left, height[j]);
        for (int j = i; j < len; j ++)
            max_right = max(max_right, height[j]);
        ret += min(max_left, max_right) - height[i];
    }
    return ret;
}

Solution2:

int trap(vector<int>& height) {
    int len = height.size();
    if (len == 0)
        return 0;
    int ret = 0;
    vector<int> max_left(len);
    vector<int> max_right(len);
    max_left[0] = height[0];
    max_right[len - 1] = height[len - 1];
    for (int i = 1; i < len; i ++) {
        max_left[i] = max(max_left[i - 1], height[i]);
    }
    for (int i = len - 2; i >= 0; i --) {
        max_right[i] = max(max_right[i + 1], height[i]);
    }
    for (int i = 0; i < len - 1; i ++) {
        ret += min(max_left[i], max_right[i]) - height[i];
    }
    return ret;
}