首页 > 代码库 > LeetCode#11. Container With Most Water

LeetCode#11. 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.

一个数组,每个代表一个高度,按(i,ai)放在坐标轴上,从中选取两个做一个容器,求最大容积。

暴力O(n2)解法

数组中的元素两两组合,O(n2),超时。

class Solution{
public:
    int maxArea(vector<int>& height) {
    int i,j,max=0,tmp;
    for(int i=0;i<height.size();++i)
        for(int j=i+1;j<height.size();++j){
            tmp=(j-i)*(height[i]<height[j]?height[i]:height[j]);
            max=tmp>max?tmp:max;
        }
    return max;
    }
};

我的O(nlogn)解法

思路

最矮的元素,如果必须选择它作容器,则最大值为最左边的元素加当前元素,或最右边的元素加当前元素。

算法

  1. 假设当前ai最数组中最矮的高度,最左边可用的高度编号是l,右边是r,则选择ai的容器,其最大容积是max(f(ai,al),f(ai,ar)),即max((i-l)*h[i]),(r-i)*h[i])),与保存的极值max比较,取最大值;
  2. 去掉当前最矮高度,调整最左和最右可用编号;
  3. 重新选择最矮高度,重复1;
  4. 当数组中仅剩下一个元素时,算法结束。

分析

这个思路先对数组排序再进行一次遍历,复杂度时O(nlogn+n),排序带来非常大的开销。另外,我的代码空间开销也很高。

代码

class SolutionOld{
public:
    int maxArea(vector<int>& height) {
    //1.Sort O(nlogn)
    int size=height.size();
    vector<pair<int,int> > vec;
    for(int i=0;i<size;++i)
        vec.push_back(pair<int,int>(height[i],i));
    sort(vec.begin(),vec.end());
    //2.Travel O(n) 当前最矮的柱子,它的最大容积,是它的高*可达到的最长的长度
    int max=0,tmp,left=0,right=size-1;
    bool *flag=new bool[size];
    for(int i=0;i<size;++i) flag[i]=0;
    for(int i=0;i<vec.size();++i){
        tmp=vec[i].first*(vec[i].second-left>right-vec[i].second?vec[i].second-left:right-vec[i].second);
        max=max>tmp?max:tmp;
        flag[vec[i].second]=true;
        while(flag[left])    ++left;
        while(flag[right])    --right;
        if(left>=right)        break;
    }
    return max;
    }
};

来自讨论区的O(n)解法

思路

先选取最宽的容器,如果其他容器容积想大于此容器,由于宽度已经减小,高度必须比最宽的容器高。

代码

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

分析

遍历一遍数组,O(n),思路很棒, 代码十分简洁优雅

LeetCode#11. Container With Most Water