42、Trapping Rain Water
题目
这道题目参考http://www.cnblogs.com/felixfang/p/3713197.html
观察下就可以发现被水填满后的形状是先升后降的塔形，因此，先遍历一遍找到塔顶，然后分别从两边开始，往塔顶所在位置遍历，水位只会增高不会减小，且一直和最近遇到的最大高度持平，这样知道了实时水位，就可以边遍历边计算面积。
代码如下：
1 class Solution { 2 public: 3 int trap(vector<int>& height) 4 { 5 const int n = height.size(); 6 if(n <= 2) return 0; 7 int max = -1, maxInd = 0; 8 int i = 0; 9 for(; i < n; ++i){//找出最大值所在位置 10 if(height[i] > max){ 11 max = height[i]; 12 maxInd = i; 13 } 14 } 15 int area = 0, root = height[0]; 16 for(i = 0; i < maxInd; ++i){ 17 if(root < height[i]) root = height[i]; 18 else area += (root - height[i]);//与最近的高点的高度差 19 } 20 for(i = n-1, root = height[n-1]; i > maxInd; --i){ 21 if(root < height[i]) root = height[i]; 22 else area += (root - height[i]); 23 } 24 return area; 25 } 26 27 };
原文：http://www.cnblogs.com/LCCRNblog/p/5054057.html