[Leetcode] container with most water 最大水容器

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.

题意：数组的值为容器的高度，下标之差为容器的宽度，求最大面积

思路：这题其实和3sum closest类似，从数组的两端，向中间遍历，计算最大面积，然后将高度较小的那端向前递进一个就行。如：3 5 8 7 6 2；开始时，面积为2*（5-0）=10；然后，尾端前进一个单位，面积为3*（4-0）=12；依次类推，取面积的最大值即可。时间的复杂度为O(n)代码如下：

 1 class Solution {
 2 public:
 3     int maxArea(vector<int> &height) 
 4     {
 5         int l=0,r=height.size()-1;
 6         int mArea=0;
 7         while(l<r)
 8         {
 9             mArea=max(mArea,(r-l)*min(height[l],height[r]));
10             height[l]<height[r]?l++:r--;
11         }
12         return mArea;
13     }
14 };

还有一种常规的思路：就是使用两个指针，一个固定，另一个从第一个的后面一个开始不断的向后遍历，求最大的面积；然后移动第一个，第二重复上述操作。这种思路用两个for循环。但时间的复杂度为O(n^2)。