对一道Twitter面试题（墙面盛水有关问题）的解答

对一道Twitter面试题（墙面盛水问题）的解答

最近同学在刷一些面试题，其中有一道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);
}