[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)代码如下：

 class Solution {

 public:

     int maxArea(vector<int> &height)

     {

         int l=,r=height.size()-;

         int mArea=;

         while(l<r)

         {

             mArea=max(mArea,(r-l)*min(height[l],height[r]));

             height[l]<height[r]?l++:r--;

         }

         return mArea;

     }

 };

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

巴特西

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

最新文章

热门文章