leetcode11
问题描述
一个数组a[i]表示数轴上i的位置有一条高度为a[i]的竖直线段，把两条线段当作一个容器左右边的高度，问，哪两条线段组成的容器容积最大。
分析问题
本质是求i<j，max{min{a[i],a[j]}}*(j-i)
解决问题
用两头扫的方法，伪代码如下：
i=0,j=n-1,best=0;
i<j:
best=max(best,min{a[i],a[j]}*(j-i))
if(a[i]<a[j]) ++i
else --j;
这里有个问题就是为什么采取a左边小的时候左边下标++，右边小的时候右边下标--的策略，最终就一定能够得到最大的一个容积呢，也就是说这种策略为什么就能够扫过最优解呢，下面我们来证明它。
证明
证明的关键就在于我们假设一边已经到了最优解的一个边界，而另外一边还没到最优解，那么没到的那边高度一定比最优解中较低的边低。
为什么呢，关键在于x轴的宽度，因为另外一边还没到最优解，所以这个时候x轴的宽度一定比最优解时的宽度宽，而这个时候如果没到的那边高度还比最优解中较低的那边高，那么这个时候容积就是已经到最优解的那条边的高度乘上现在x轴的宽度，这个乘积已经大于最优解了。所以只能是没到的那边高度一定比最优解中较低的那边低。
算法实现
class Solution{
public:
int maxArea(vector<int>& height){
int best=0;
int n=height.size();
for(int i=0,j=n-1;i<j;){
best=max(best,min(height[i],height[j])*(j-i));
if(height[i]<height[j]){
i++;
}
else{
j--;
}
}
return best;
}
}