11. Container With Most Water
- Total Accepted: 86363
- Total Submissions: 244589
- Difficulty: Medium
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.(不能倾斜容器)
思路：
这道题很简单，大概意思是要找到两条条纵线然后这两条线以及X轴构成的容器能容纳最多的水。而任意两条线与x轴一起能装的水的最大量就是两条线在x轴的距离乘以较矮的那条线的高度即可。所以解题思路就很简单了。
方法一：
暴力求法，求每一种情况下的最大装水面积，然后比较是否最大，不是则下一种，是则替换为当前最大值。
public int maxArea2(int[] height) {
int n = height.length ;
if(height == null || n < 2){
return 0 ;
}
int max = 0 ;
for(int i = 0 ; i < n ; i++){
for(int j = i+1 ; j < n ; j++){
int low = height[i]<height[j]?height[i]:height[j] ;
int area = low*(j-i)/2 ;
max = max>area?max:area ;
}
}
return max ;
}
方法二：
最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到左边大于右边为止就行了。
注意：如果将较短的边向中间移后，新的边还更短一些，其实可以跳过，减少一些计算量
public int maxArea(int[] height) {
int n = height.length ;
if(height == null || n < 2){
return 0 ;
}
int max = 0 ;
int left = 0 ;
int right = n-1 ;
while(left < right){
int low = height[left]<height[right]?height[left]:height[right] ;
int area = low*(right-left) ;
max = max>area?max:area ;
if(low == height[left]){
left++ ;
}else{
right-- ;
}
}
return max ;
}