`
bcyy
  • 浏览: 1809764 次
文章分类
社区版块
存档分类
最新评论

LeetCode Container With Most Water 查找容水量最大的容器 动态规划法思想分析

 
阅读更多

Givennnon-negative integersa1,a2, ...,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpoints of lineiis 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.

注意这里的Note:和装的东西是水,就是最短木板原理:一个桶能装多少水是由最短的那块木板决定的。

一开始没搞清楚这一点,误以为是比较梯形的面积,所以做错了。

其实这个是动态规划法做的,因为我没看到有人分析其中的动态规划法思想,所以在这里分析一下。

下面分析是怎么样的动态规划法思想。

1 分区,首先分最大区间,左边高度为height[0],右边高度为height[n-1], 分一个区间,那么这个区间的解肯定是height[0]和height[n-1]围成的区间

2 区间细分,分两个区间height[0]和height[n-2],还有height[1]和height[n]也构成一个区间,这个区间的最大木桶容水量和前面比较,这个值也可以用表保存下来,但是因为我们不需要中间结果,所以不需要保存一个表,只需要保存最大值就可以了。

3 继续细分为3个区间,然后4个区间,……直到n-1个区间。

但是这道题就巧妙的利用了一个木桶和装水的特征,可以更加优化一点。不过其实也是动态规划法原理。至于怎么利用这个特征,很多博客都有分析了,我就不在这里重复了。随便百度就可以了。我只是没看到有人分析这里的动态规划法的思想,所以分析一下。

看看LeetCode上有人贴出的程序:

http://discuss.leetcode.com/questions/193/container-with-most-water

int maxArea(vector<int> &height) {
		int i = 0;
		int j = height.size() - 1;
		int res = 0;
		while(i < j)
		{
			int temp = min(height[i], height[j]) * (j - i);
			if(temp > res)
				res = temp;
			if(height[i] <= height[j])
				i++;
			else
				j--;
		}
		return res;
	}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics