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 and n is at least 2.
image.png
这题简单说就是 给一个数组
让你返回这个数组的最大“面积”。
比如 一个数组区间 [a:b] ， 那么他的“面积” 就是 min(a,b) * (b-a)
O(n2)
暴力的方法就是 枚举所有情况，这个很容易想到。
class Solution {
public:
int maxArea(vector<int>& height) {
int _max = 0;
int temp = 0;
for(int i =0; i < height.size();i++){
for(int j = i+1 ; j<height.size();j++){
temp = min(height[i],height[j])*(j-i);
_max = temp > _max? temp: _max;
}
}
return _max;
}
};
image.png
O（n）
我们发现他的“面积”会受到 两边界 a 点 和 b 点的最低高度影响，如果[a,b]内有一个高点， 那么他会选择 和 a,b 两点中 高度大的点 组成最大面积。
所以我们从 整个数组的两边界（0, n-1）开始， 不断淘汰 边界较小的点，更新最大值 。
这样我们就同时保证了[a,b] 的长度是最大的，并且a, b 都是彼此搭配最高的。
class Solution {
public:
int maxArea(vector<int>& height) {
int _max = 0;
int temp = 0;
int i = 0;
int j = height.size()-1;
while(i<j){
temp = min(height[i],height[j])* (j-i);
_max = temp>_max? temp : _max;
if (height[i]<= height[j])
i++;
else
j--;
}
return _max;
}
};
image.png
