问题描述
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)解法
思路
最矮的元素，如果必须选择它作容器，则最大值为最左边的元素加当前元素，或最右边的元素加当前元素。
算法
- 假设当前ai最数组中最矮的高度，最左边可用的高度编号是l，右边是r，则选择ai的容器，其最大容积是max(f(ai,al),f(ai,ar))，即max((i-l)*h[i]),(r-i)*h[i]))，与保存的极值max比较，取最大值；
- 去掉当前最矮高度，调整最左和最右可用编号；
- 重新选择最矮高度，重复1；
- 当数组中仅剩下一个元素时，算法结束。
分析
这个思路先对数组排序再进行一次遍历，复杂度时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)，思路很棒， 代码十分简洁优雅