题目连接：Leetcode 042 Trapping Rain Water
解题思路：从左向右遍历一遍，保存每个位置往左的最高值。再从右往左遍历一遍，保存每个位置往右的最高值。最后遍历一遍数组，取左右最高值中较小的一个，减去当前值，即为这个位置增加的量。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(), h;
int* l = new int[n];
int* r = new int[n];
h = 0;
for (int i = 0; i < n; i++) {
h = max(h, height[i]);
l[i] = h;
}
h = 0;
for (int i = n-1; i >= 0; i--) {
h = max(h, height[i]);
r[i] = h;
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += min(l[i], r[i]) - height[i];
delete l;
delete r;
return ans;
}
};
