leetcode之路011 Container With Most Water

题目大意：给定n个非负的整数a1,a2...ai，每个点表示一个坐标(i,ai)，从坐标轴上画n条直线，分别是连接(i,0)和(i,ai)的。其中任意两条直线看成一个容器，向里面装水，现在要找到所有容器中能容纳的水最多为多少。

意思是两条直线，一个高位h1，另一个为h2，装水的高度最多为h1。

思路一：直接遍历求解，复杂度O(n^2)

对每一条直线，求出它和其它所有直线所构成容器的盛水大小mm，当mm大于前面的最大值，则更新。

即需要两个for循环，外层i为0-size()-1,内层j为i+1到size-1。这是最简单的实现，但是时间复杂度太高，抱着测试leetcode对时间的要求是否严格，编写了一下进行提交。果然，显示超时，看来此题不能容忍O(n^2)的复杂度，下面是超时此思路的代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
		int i,j;
		int resu=0,mm;
		if(height.size()==0||height.size()==1)
			return 0;
		for(i=0;i<height.size();++i)
		{
			for(j=i+1;j<height.size();++j)
			{
				mm=(j-i)*min(height[i],height[j]);
				if(mm>resu)
					resu=mm;
			}

		}	
		return resu;
    }
};
           

思路二：复杂度为O(n)

由于是计算矩形的面积，而x轴最大为size，假如固定长从大到小进行遍历，此时，只需要考虑高度对面积的影响了。

1、设定两个指针fi和la，分别指向数组的头元素和尾元素，判断两个元素的大小，即高度，分以下三种情况

a:height[fi]<height[la]时，此时fi和其它元素组成的容器必定小于和la组成的容器。原因，如下图所示，fi和其它元素组成容器时，高度最大只能为fi的高度(可能更小，如下图中间直线所示)，而长度必定小于la-fi，所以相乘的结果也更小。此时只需fi++即可。

b:height[fi]>height[la]时，同上可知，此时la和其它元素组成的容器必定小于和fi组成的容器，此时只需la--即可。

c:height[fi]=height[la]时，此时无论fi或者la和其它哪一个元素组成容器，必定小于fi和la组成的容器，此时fi++，la--即可。

下面是ac的代码，运行时间为24ms，在提交代码里已经是最快了：

class Solution {
public:
    int maxArea(vector<int>& height) {
		int mm=0;
		if(height.size()==0||height.size()==1)
			return 0;
		int fi=0,la=height.size()-1;
		int mm_temp;
		mm=(la-fi)*min(height[fi],height[la]);
		while(fi<la)
		{
			if(height[fi]<height[la])
				++fi;
			else if(height[fi]>height[la])
				--la;
			else
			{
				++fi;
				--la;
			}
			mm_temp=(la-fi)*min(height[fi],height[la]);
			if(mm<mm_temp)
				mm=mm_temp;
		}
		return mm;
    }
};
           

讨论区的算法也是如此，但实现得更简洁一点，如下：

class Solution {
public:
    int maxArea(vector<int> &height)
    {
        int j=height.size()-1,i=0,mx=0;
        while(i<j)
        {
            mx=max(mx,((j-i)*(min(height[i],height[j]))));

            if(height[i]<height[j])
             i++;
             else if(height[i]>=height[j])
             j--;
        }
        return mx;
    }
};
           

2016.09.04 更新 JAVA代码：

public class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int low = 0;
        int high = height.length - 1;
        while(low < high){
            if(height[low] <= height[high]) {
                max = Math.max(max, (high - low) * height[low]);
                low++;
            } else {
                max = Math.max(max, (high - low) * height[high]);
                high--;
            }
        }
        return max;
    }
}