Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
39 lines (35 sloc) 1.37 KB
problem:
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.
-------------------------------------------------
solution:
这题关键点是理解好题意。题目的目的是找两条垂直线组成的容器,使这个容器能装下最多的水,而与这两条垂直线之间的任何线长短是是没有关系的。
从两头到中间扫描,设i,j分别指向height数组的首尾。
那么当前的area是min(height[i],height[j]) * (j-i)。
当height[i] < height[j]的时候,我们把i往后移,否则把j往前移,直到两者相遇。
int maxArea(vector<int> &height)
{
if(height.size() < 2)
return 0;
int i = 0;
int j = height.size() - 1;
int maxarea = 0;
while(i < j)
{
int area = 0;
if(height[i] < height[j])
{
//因为i是短板,所以如果无论j往前移动到什么位置,都不可能产生比area更大的面积
//换句话所,i能形成的最大面积已经找到了,所以可以将i向前移。
area = height[i] * (j - i);
i++;
}
else
{
area = height[j] * (j - i);
j--;
}
maxarea = max(maxarea, area);
}
return maxarea;
}