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轴的距离乘以较矮的那条线的高度即可。所以解题思路就很简单了。
暴力求法,求每一种情况下的最大装水面积,然后比较是否最大,不是则下一种,是则替换为当前最大值。
1 public int maxArea2(int[] height) {
2 int n = height.length ;
3 if(height == null || n < 2){
4 return 0 ;
5 }
6 int max = 0 ;
7 for(int i = 0 ; i < n ; i++){
8 for(int j = i+1 ; j < n ; j++){
9 int low = height[i]<height[j]?height[i]:height[j] ;
10 int area = low*(j-i)/2 ;
11 max = max>area?max:area ;
12 }
13 }
14 return max ;
15 }
最大盛水量取决于两边中较短的那条边,而且如果将较短的边换为更短边的话,盛水量只会变少。所以我们可以用两个头尾指针,计算出当前最大的盛水量后,将较短的边向中间移,因为我们想看看能不能把较短的边换长一点。这样一直计算到左边大于右边为止就行了。
注意:如果将较短的边向中间移后,新的边还更短一些,其实可以跳过,减少一些计算量
1 public int maxArea(int[] height) {
2
3 int n = height.length ;
4 if(height == null || n < 2){
5 return 0 ;
6 }
7 int max = 0 ;
8 int left = 0 ;
9 int right = n-1 ;
10 while(left < right){
11 int low = height[left]<height[right]?height[left]:height[right] ;
12 int area = low*(right-left) ;
13 max = max>area?max:area ;
14 if(low == height[left]){
15 left++ ;
16 }else{
17 right-- ;
18 }
19 }
20 return max ;
21 }