本文共 986 字，大约阅读时间需要 3 分钟。

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.

For example,

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!

很有意思的一道题，借鉴大神的思路：用两个数组分别记录某点左边最大高度，右边最大高度，然后取最小值，最后求出最小值与该点的实际高度只差，若大于0则原来计算的储水量增加该差值，否则，不增加。

int trap(int* height, int heightSize) {    if(height==NULL || heightSize<1)return 0;      int leftMax[1000];    int rightMax[1000];    int max = 0;    int water=0;    int i;    for(i = 0;i
   
    height[i]?max:height[i];    }    max = 0;    for(int j =heightSize -1;j>=0;j--){        rightMax[j] = max;        max = max>height[j]?max:height[j];    }    for(i=0;i
    
     rightMax[i]?rightMax[i]:leftMax[i];        int h = min - height[i];        if(h>0)           water+=h;    }    return water;}
    
   

转载地址：http://ljtsi.baihongyu.com/