Brute force

Each bar: min(left_max, right_max) - cur_height decides how much rain water can be stored.

C++: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int trap(vector<int>& height) {
    if (height.empty()) return 0;
    int res = 0, size = height.size();
    vector<int> left_max(size), right_max(size);
    left_max[0] = height[0];
    for (int i = 1; i < size; ++i) {
        left_max[i]= max(left_max[i-1], height[i]);
    }
    right_max[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; --i) {
        right_max[i] = max(right_max[i+1], height[i]);
    }
    for (int i = 1; i < size - 1; ++i) {
        res += min(left_max[i], right_max[i]) - height[i];
    }
    return res;
}

two pointer

比较subtle，不过实际上跟上面的思路类似；
双指针left和right向中间靠近, 因为当前bar的water量是由左右最高点两个中比较低的那个决定的，所以e.g. leftMax < rightMax的时候，只用移动left向右，寻找更高的高度就行了，因为此时高度差跟right高度并没有关系，所以只用移动左边的；反过来的时候只用移动右边的.

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int trap(int[] height) {
    if (height.length == 0) return 0;
    int left = 0, right = height.length - 1;
    int maxL = height[left], maxR = height[right];
    int res = 0;
    
    while (left < right) {
        if (maxL < maxR) {
            res += maxL - height[left];
            maxL = Math.max(maxL, height[++left]);
        } else {
            res += maxR - height[right];
            maxR = Math.max(maxR, height[--right]);
        }
    }
    return res;
}