No.011 Container With Most Water

时间:2023-03-31 10:26:01

11. Container With Most Water

  • Total Accepted: 86363
  • Total Submissions: 244589
  • Difficulty: Medium

  Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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 ;
}