LeetCode–Container With Most Water

2015年6月24日 | 分类: 日志 | 标签:

题目:

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

其实一开始并没有看出来最优解,网上搜索到答案才知道的:

最优解法非常巧妙,利用了常见的”双指针”法, 两个指针一个指向最前,一个指向最后, 然后 “数值小”的指针向里运动, 这里利用了”水桶的容积只取决于最短的那个木板”的原理!,最终把复杂度降到了O(n)

container-with-most-water-400x161

不过我想了半天才明白了为什么如此移动指针的方法可以确保能够遍历到容积最大的组合:

1.整个搜索过程可以理解为遍历水桶的宽度从n-1到1,只要遍历到每个宽度的最大容积组合就可以保证得到正确的结果。

2.假定ax是a1~ax里最大值,ay是ay~an里的最大值,可以推断出宽度为y-x的水桶组合里,x~y的容积是最大。因为水桶的容积只取决于最短的那块木板,宽度确定的情况下,无论这个组合左移或者右移都无法使得最短的那块木板长度增加。

3.假定ax是a1~ax里最大值,ay是ay~an里的最大值,宽度w=y-x (即第x块木板不低于所有左侧的木板高度,第y块木板不低于所有右侧的木板高度)

先假定ax<=ay,i是满足ax+i>ax的最小值,即第x+i块木板是第x块木板右边第一个更高的木板,由水桶原理可推断出所有宽度小于w但大于w-i+1的组合不可能比当前组合的容积更高(因为ax是a1~ax+i-1里的最大值,ay>ax,宽度减小但是较短的那个木板高度不会变的更高),此时x+i~y的容积是有可能超过x~y的容积,需要计算来判断。

同理如果ax>ay则从y往左找到第一块更高的木板。

4.从宽度n开始,根据3即可找到最大的容积。即,每次移动两侧较低的那块木板向另外一侧,直到该木板的高度高于移动前的高度,然后比较是否大于当前找到的最大容积。

 

下面是我的代码供参考:

#define MIN(x, y) ((x) > (y) ? (y) : (x))

int maxArea(int* height, int heightSize) {
	int lh = height[0], rh = height[heightSize - 1];
	int l = 0, r = heightSize - 1;

	int h, max_area;
	max_area = 0;

	while (l < r)
	{
		int area = (r - l) * MIN(height[l], height[r]);
		if (area > max_area)
			max_area = area;

		if (height[l] < height[r])
		{
			h = height[l];
			while ((height[l] <= h) && (l < r))
				l++;
		}
		else
		{
			h = height[r];
			while ((height[r] <= h) && (l < r))
				r--;
		}

	}

	return max_area;
}
目前还没有任何评论.

[cusFace:84] [cusFace:83] [cusFace:82] [cusFace:79] [cusFace:67] [cusFace:66] [cusFace:65] [cusFace:54] [cusFace:53] [cusFace:52] [cusFace:51] [cusFace:50] [cusFace:49] [cusFace:48] [cusFace:47] [cusFace:44] [cusFace:43] [cusFace:42] [cusFace:41] [cusFace:40] [cusFace:39] [cusFace:38] [cusFace:37] [cusFace:36] [cusFace:35] [cusFace:34] [cusFace:33] [cusFace:32] [cusFace:31] [cusFace:30] [cusFace:29] [cusFace:28] [cusFace:27] [cusFace:26] [cusFace:25] [cusFace:24] [cusFace:23] [cusFace:22] [cusFace:21] [cusFace:20] [cusFace:19] [cusFace:18] [cusFace:17] [cusFace:16] [cusFace:15] [cusFace:14] [cusFace:13] [cusFace:12] [cusFace:11] [cusFace:10] [cusFace:09] [cusFace:08] [cusFace:07] [cusFace:06] [cusFace:05] [cusFace:04] [cusFace:03] [cusFace:02] [cusFace:01] [cusFace:00]