题目描述
给定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;
    }