42. 接雨水

难度困难

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

 

 

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路：先找出最高的柱子的下标，然后从两边向最高山峰求解，因为接水的前提是左右要有两根柱子中间才可以接水，如果左右两根柱子高度不等，则接水格子应取最低的柱子为接水的高限度，由于知道了最高的柱子所以从两头向最高主子遍历时只需判断接下来的柱子高度是否低于这个元素，如果高于，刷新下标，否则，将接水的格子累加。

 1 int trap(int* height, int heightSize){
 2     if(heightSize<2){
 3         return 0;
 4     }
 5     int i=0,j,cmp=0,HeightFlag,max=height[0];
 6     for(i=1;i<heightSize;i++){
 7         if(height[i]>max){
 8             max=height[i];
 9         }
10     }
11     for(i=0;i<heightSize;i++){
12         if(height[i]==max){
13             break;
14         }
15     }
16     HeightFlag=i;
17     for(i=0,j=i+1;j<HeightFlag;j++){
18         if(height[i]>=height[j]){
19             cmp+=(height[i]-height[j]);
20         }else{
21             i=j;
22         }
23     }
24     i=heightSize-1;
25     for(j=i-1;j>HeightFlag;j--){
26         if(height[i]>height[j]){
27             cmp+=(height[i]-height[j]);
28         }else{
29             i=j;
30         }
31     }
32     return cmp;
33 }