容器短板問題
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ù)代表一個坐標點楚里。以此點做關于x軸的垂線午衰，這樣會有n條垂直于坐標軸的垂線蚤吹，其中任意兩條線可以構(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;
}
};
