[twitter] 墙之间的水坑能够装多少水

“在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表，数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]”

“假如开始下雨了，那么墙之间的水坑能够装多少水呢？”

解决思路：

1 初始化左指针为元素0的值，初始化右指针为元素size-1的值。

2 如果（左指针找到的左指针以左的最大值）小于（右指针找到右指针以右的最大值），将左指针向右移动一位。否则右指针向左移动一位。重复过程直到两个指针相遇。

实现代码：

#include <iostream>
using namespace std;
int Calc(int[], int);
int main()
{
	int testcase_1[] = {2,5,1,2,3,4,7,7,6};
	int testcase_2[] = {2,5,1,3,1,2,1,7,7,6};
	int testcase_3[] = {6,1,4,6,7,5,1,6,4};
	int testcase_4[] = {1,2,4,6,7,8,7,6,4};
	cout<<Calc(testcase_1,9)<<endl;
	cout<<Calc(testcase_2,10)<<endl;
	cout<<Calc(testcase_3,9)<<endl;
	cout<<Calc(testcase_4,9)<<endl;
}

int Calc(int a[], int size)
{
	int left = 0;
	int right = size - 1;
	int max_left = a[left];
	int max_right = a[right];
	int sum = 0;
	while(left < right)
	{
		if (a[left] < a[right])
		{
			left++;
			if (a[left] > max_left)
			{
				max_left = a[left];
			}
			else
			{
				sum += max_left - a[left];
			}
		}
		else
		{
			right--;
			if (a[right] > max_right)
			{
				max_right = a[right];
			}
			else
			{
				sum += max_right - a[right];
			}
		}
	}

	return sum;
}

输出结果：

10

17

13

0