最近同学在刷一些面试题，其中有一道Twitter的题目很有意思：
看下面这个图片”
“在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表，数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]”“假如开始下雨了，那么墙之间的水坑能够装多少水呢？”
我的算法思路如下：
将水坑中的水按照水平方向进行切分，划分成若干“横向水条”，如下图所示（手画的图，，有点丑）：
1.采用遍历的方法，依次遍历数组中的每个数字（从第2个元素遍历到倒数第2个元素）；
2.对于当前数字temp，向前（下标递减方向）找到第一个比当前数字大的数，记为high1，再向后（下标递增方向）找到第一个比当前数字大的数，记为high2；
3.比较high1和high2中，记其中的小的数字为hi；
4.通过计算hi和temp之间的“横向水条的面积”，最后相加
5.其中mark是为了避免对同一高度的水条进行多次计算。。
具体实现代码如下：
#include <stdio.h>int water(int a[], int len){int hi,high1,high2,temp,wat,index1,index2,sum=0;int mark[100]; //该数组用于标识墙所在高度的行是否已被装水for(int i=0;i<100;i++)mark[i]=0; //标识为0表示还未被装水for(int j=1;j<len-1;j++){high1=-1;high2=-1;if(mark[j]==1)continue;temp=a[j];for(int k=j+1;k<len;k++){if(a[k]<temp)continue;else if(a[k]==temp){mark[k]=1;continue;}else{high1=a[k];index1=k;break;}}for(int m=j-1;m>=0;m–){if(a[m]<=temp)continue;else{high2=a[m];index2=m;break;}}if(high1==-1||high2==-1)continue;hi=high1;if(high2<hi)hi=high2;wat=(hi-temp)*(index1-index2-1);sum=sum+wat;}return sum;}void main(){int a[10]={2,5,1,3,1,2,1,7,7,6};int result=water(a,10);printf("%d",result);}
世界上那些最容易的事情中，拖延时间最不费力。
