LeetCode Container With Most Water

LeetCode Container With Most Water

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.


题意是x轴上立着一堆线段,从这些线段中找两根和x轴构成一个木桶,问哪个木桶能装最多的水。

暴力枚举的话,是O(n^2)的。我们可以用贪心的思路来解决:要使木桶装更多的水,短板越长越好,且两根线之间的距离越长也越好。

设置首尾指针i,j,计算由i,j夹到的木桶的体积(这里简单点,面积即可),如果height[i]<height[j],则i++,因为短板越长越好,所以这相当于抛弃了height[i],保留height[j],底板减1。

完整代码如下:

class Solution {
public:
	int maxArea(vector<int>& height) {
		int mA = 0, i = 0, j = height.size() - 1;
		while (i != j)
		{
			int cur = min(height[i], height[j])*(j - i);
			if (cur > mA)
				mA = cur;
			if (height[i] < height[j])
				i++;
			else
				j--;
		}
		return mA;
	}
};

本代码提交AC,用时24MS。

二刷。

证明贪心方法的正确性一般用反证法,推出矛盾即可,证明过程见讨论区:https://discuss.leetcode.com/topic/503/anyone-who-has-a-o-n-algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *