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.
Example
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
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!
Discussion
观察装水后的图像可以看出，这时一个从两边向中间逐渐升高的过程。
首先，我们遍历数组找到最大值。然后从左边向最大值靠近，如果右边的比左边的地势低，就可以装水。从右向左类似。
算法的时间复杂度为O(n)。
C++ Code
class Solution {
public:
int trap(vector<int>& height) {
int max_ele = 0;
int max_pos = 0;
//找到最高点
for (int i = 0; i < height.size(); i++) {
if (height[i] > max_ele) {
max_ele = height[i];
max_pos = i;
}
}
int trapped_rain = 0;
//从左向最高点遍历
for (int i = 1; i < max_pos; i++) {
if (height[i] < height[i - 1]) {
trapped_rain += height[i - 1] - height[i];
height[i] = height[i - 1];
}
}
//从右向最高点遍历
for (int i = height.size() - 2; i > max_pos; i--) {
if (height[i] < height[i + 1]) {
trapped_rain += height[i + 1] - height[i];
height[i] = height[i + 1];
}
}
return trapped_rain;
}
};