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.
思路: 设Hight[i]为第i个line的高度,设立两个指针left和right初始分别指向最左端和最右端,maxArea由此得到初始面积。然后左指针不断右移,右指针不断左移直到他们相交并由此更新最大面积。移动规则如下:
if (Height[left] < Height[right])
left++
else
right--
即如果左指针小,那么左指针右移。如果右指针小,那么右指针左移。
先贴出代码,再证明为什么这种移动法能够得到最大面积。
class Solution {
public:
int maxArea(vector<int> &height) {
int left = , right = height.size()-;
int max_area= ;
while (left < right) {
int tmp = area(min(height[left], height[right]), right - left);
if (max_area < tmp)
max_area = tmp;
if (height[left] < height[right])
++left;
else
--right;
}
return max_area;
}
private:
int area(int x, int y){
return x*y;
}
};
下面证明这种方法可以得到最大面积:
首先我们需要知道,left和right指针一定会遍历所有端点,且它们不会有公共的遍历点。
然后我们可以先假设已经知道了最大面积,并设其左端点为leftMax,右端点为rightMax,且不妨设Height[leftMax] < Height[rightMax]。我们需要证明的是存在某一个时刻使得left=leftMax and right=rightMax
由于两个端点构成了最大面积,那么可以得到
(1) Height[left] < Height[leftMax] (1 <= left < leftMax) 且
(2 ) Height[right] < Height[leftMax] (leftMax+1 <=right <=totalNum)
根据假设:
(3) Height[leftMax] < Height[rightMax]
那么根据算法的规则:如果左端点比右端点小,左端点右移,反之亦然。那么由此可得:
(4)如果left先到达leftMax,而right还未到达rightMax,那么根据(2),right一定会一直移动到rightMax而left呆在leftMax不动
(5)如果right先到达rightMax,而left还未达到leftMax,那么根据(1)和(3),left一定会一直移动到leftMax而right呆在rightMax不懂。
根据(4)和(5)得到一定存在某一个时刻使得left=leftMax and right=rightMax。