数据能够形成的最大容器

题目描述
给定n个非负整数a1，a2，…，an，其中每个数字表示坐标(i, ai)处的一个点。以（i，ai）和（i，0）（i=1,2,3...n）为端点画出n条直线。你可以从中选择两条线与x轴一起构成一个容器，最大的容器能装多少水？

例如：
输入 [1,8,6,2,5,4,8,3,7]
输出: 49
思路分析与方法
要求选择两条线与x轴一起构成一个容器，问能够形成的最大容量。我们可以依次遍历数据，分别把第i个数据当做最短边，然后在前面(从第一个数据向后寻找)和后面(从最后一个数据向前寻找)的数据中找出大于等于该数据的最长的边，这样就可以在O(n^2)复杂度下得到最大的面积，代码如下。

int maxArea(vector<int>& height) 
    {
        if(height.size()<2) //数据太少构成不了容器，自然其容量就是0
            return 0;
        int maxArea=0;
        int tmpArea=0;
        int longest=0;
        for(int i=0;i<height.size();++i)
        {
            //以第i个数据为最短边，分别向左向右找到最大边长
            longest=0;
            int idx=0;
            while(idx<i)
            {
                if(height[idx]>=height[i])
                {
                    longest=i-idx;
                    break;
                }
                ++idx;
            }
            idx=height.size()-1;
            while(idx>i && idx-i>longest)
            {
                if(height[idx]>=height[i])
                {
                    longest=idx-i;
                    break;
                }
                --idx;
            }
            tmpArea=height[i]*longest;
            if(tmpArea>maxArea)
                maxArea=tmpArea;
        }
        return maxArea;
    }

另一种方法是从两边向中间靠拢，得到面积的最大值，具体做法是，让i指向第一个数据，j指向最后一个数据，计算当前以第i个数据为左端点，第j个数据为右端点时形成的面积，依次让两个数据中的较小值向中间移动，每次计算当前面积并更新最大面积。
证明为什么这样可以找到最大值，假设第x个数据和第y个数据形成的容器是最大的，我们让i从第一个出发，j从最后一个出发，如果i到达x，j还大于y，这时一定有height[j]<height[i]（下面证明这个不等式，假如height[j]>height[x],那么这时的面积是height[i](j-x)，这个面积一定比最优时的面积min(height[x],height[y])(y-x)大，那么就与假设矛盾了）且还有height[j]<height[y]，证明同前面的，这样我们每次让较小的向中间移动一定不会错过最优解。同理i还小于x，j已经到达y的情况也一样。代码如下。

int maxArea(vector<int>& height) 
    {
        if(height.size()<2) //数据太少不能构成容器
            return 0;
        int i=0,j=height.size()-1;
        int maxArea=0;
        int tmpArea=0;
        while(i<j)
        {
            tmpArea=min(height[i],height[j])*(j-i);
            if(tmpArea>maxArea)
                maxArea=tmpArea;
            if(height[i]<height[j])
                ++i;
            else
                --j;
        }
        return maxArea;
    }