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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

楚兴 2015-02-04 12:59:00 浏览725
展开阅读全文


“在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表,数组中每个数是墙的高度。上边的图可以表示为数组[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

网友评论

登录后评论
0/500
评论
楚兴
+ 关注