能够想到的最传统的方法：
class Solution {
public:
int maxArea(vector& height) {
int len=height.size();
int maxarea=0;
int area;
int heightmin;
for (int i=0;i
for(int j=i;j
heightmin=min(height[i],height[j]);
area=heightmin*(j-i);
maxarea=(maxarea>area)?maxarea:area;
}
}
return maxarea;
}
};
相当于将所有的Cn2种情况都遍历了一遍。
erro.JPG
样本特别大就没办法啦。会超时的。
那么！时间复杂度小很多的解法！
从两头找。较短的那一条边往中间移一个！
因为如果是长的那个移动，无论如何水的高度都不会高过短的那条边了，面积肯定不会增加的。只有改变短的才有希望！
天哪太机智了！！
class Solution {
public:
int maxArea(vector<int>& height) {
int len=height.size();
int maxarea=0;
int area;
int heightmin;
int i=0;
int j=len-1;
while(j-i>0)
{
if (height[i]<height[j])
{area=height[i]*(j-i);
i++;}
else
{ area=height[j]*(j-i);
j--;}
maxarea=(maxarea>area)?maxarea:area;
}
return maxarea;
}
};
