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,
Given [0,1,0,2,1,0,1,3,2,1,2,1],return 6.
思路：每个数代表了柱子的高度，求总的成水量。最初的思路是这样的：首先找到最高的柱子，然后找第二高的柱子，它们之间的成水量，就是第二高的柱子的高度，乘以它们之间的距离，然后减去它们中间的所有柱子的面积（高度）。这两根柱子就形成了一个边界，然后依次去找第三高，第四高...的柱子，分别求出它们与边界之间的成水量即可。
既然要从大到小寻找柱子，那么就得排序，按照高度从大到小排序，主要是记录这些柱子的索引。代码如下：
typedef struct
{
int value;
int index;
}Node; //辅助结构，记录高度和索引，按照高度从大到小排序
#define min(x,y) (((x)<(y))?(x):(y))
void swapnode(Node*n1, Node *n2)
{
Node tmp;
tmp.value = n1->value;
tmp.index = n1->index;
n1->value = n2->value;
n1->index = n2->index;
n2->value = tmp.value;
n2->index = tmp.index;
}
//下面是对Node结构的快速排序，从大到小。
int partition(Node*nset, int left, int right)
{
int key = nset[right].value;
int i = left-1;
int j;
for(j = left; j <right; j++)
{
if(nset[j].value >key)
{
i++;
swapnode(nset+i,nset+j);
}
}
swapnode(nset+i+1,nset+right);
return i+1;
}
void qsortnode(Node*nset, int left, int right)
{
int q = -1;
if(left < right)
{
q = partition(nset,left, right);
qsortnode(nset, left,q-1);
qsortnode(nset, q+1,right);
}
}
//主函数
int trap(int*height, int heightSize)
{
if(heightSize <= 2)return0;
Node *vi = calloc(heightSize,sizeof(Node));
int i;
int sum = 0;
int left, right, minvalue;
//首先对辅助结构进行排序，主要是得到他们的索引顺序
for(i = 0; i <heightSize; i++)
{
vi[i].value = height[i];
vi[i].index = i;
}
qsortnode(vi, 0, heightSize-1);
//以最高的柱子为边界
left = right = vi[0].index;
sum = 0;
for(i = 1; i <heightSize; i++)
{
int index = vi[i].index;
int value = vi[i].value;
/*如果该柱子已经处于边界中，则需减去他们的面积，因为在得到边界的时候，已经将这些柱子计算在内了。*/
if(index < right &&index > left)
{
sum -= value;
}
/*扩展左边界，计算边界内的盛水总面积，包括中间柱子的面积*/
else if(index <left)
{
sum += height[index]* (left-index-1);
left = index;
}
/*扩展右边界，计算边界内的盛水总面积，包括中间柱子的面积*/
else if(index >right)
{
sum += height[index]* (index-right-1);
right = index;
}
}
return sum;
}上面的算法不是最优的，时间复杂度为O(nlogn)，空间复杂度为O(n)。leetcode上的测试时间是8ms。时间和空间主要浪费在排序上了，其实可以不用排序的。思路如下：
首先找到最高的柱子，以它为隔板，将整个数组分成左右两部分。左半部分中，从左到右依次扫描，因为隔板的存在，所以只要左边的柱子比右边高，则高度差就可以盛水。右半部分同理。这种算法的时间复杂度为O(n)，空间复杂度为O(1)。leetcode上的测试时间是4ms。代码如下：
int trap_nb(int*height, int heightSize)
{
int i;
int sum = 0;
int maxindex = 0;
int prehight = 0;
//找最高柱子的索引
for(i = 1; i <heightSize; i++)
{
if(height[i] >height[maxindex])
{
maxindex = i;
}
}
//从左到右扫描，计算高度差
prehight = 0;
for(i = 0; i <maxindex; i++)
{
if(height[i] >prehight)
{
prehight = height[i];
}
sum += prehight - height[i];
}
//从右到左扫描，计算高度差
prehight = 0;
for(i = heightSize-1;i > maxindex; i--)
{
if(height[i]> prehight)
{
prehight = height[i];
}
sum += prehight - height[i];
}
return sum;
}
参考： https://github.com/haoel/leetcode/blob/master/algorithms/trappingRainWater/trappingRainWater.cpp