容器短板問題
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 and n is at least 2.
大致意思：給定n個非負整數(shù)a1,a2,...,an，每一個整數(shù)代表一個坐標(biāo)點。以此點做關(guān)于x軸的垂線，這樣會有n條垂直于坐標(biāo)軸的垂線，其中任意兩條線可以構(gòu)成一個容器，找到這樣的兩
條線構(gòu)成的容器能夠裝盡可能多的水。
注意：其中n至少為2，也就是說至少存在一個容器。
提示：首先需要明白一點，兩條線組成的容器，能夠容納的水量是最短的那根線決定。可以看下圖輔助理解。
容器圖
常規(guī)解法：我們可以將a1和an這兩條邊界線組成的容器作為初始容器，先求出兩根線中的最短的線做為高，記容器高H=min(a1,an)，記容器的長L=(n-1)，初始容器體積為V=L*H。計算容器容積時要考慮到長的因素，以H為高的其他任何容器都不會比初始容器體積大，因為其他容器的高（最短的線）最大為H，而長必定小于L，所以a1和an中小的那條線在后續(xù)比較中就可以不考慮了。如果H==a1，說明a1是最小的，肯定小于初始容器體積，我們繼續(xù)看a2和an組成的容器，否則查看a1和an-1組成的容器，同時更新最大容器值。依照這樣的策略逐步縮小范圍，最終就得到了最大容器。
class Solution {
public:
int maxArea(vector<int>& height) {
int n=height.size();
int maxa=0,i=0,j=n-1;
while(i<j)
{
maxa=max(maxa,min(height[i],height[j])*(j-i));
if(height[i]>height[j])
--j;
else
++i;
}
return maxa;
}
};
