首页 > 代码库 > Leetcode Container With Most Water
Leetcode Container With Most Water
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.
对于这道题，首先用的是暴力求解法，复杂度为O（n2），
1 package Container.With.Most.Water; 2 3 public class ContainerWithMostWater { 4 5 /** 6 * @param args 7 */ 8 public static void main(String[] args) { 9 // TODO Auto-generated method stub10 int height[]={1,2,3,4};11 int maxArea=maxArea(height);12 System.out.println(maxArea);13 }14 15 public static int maxArea(int[] height) {16 int maxArea=0;17 for(int i=0;i<height.length;i++){18 for(int j=i+1;j<height.length;j++){19 int minHeight=Math.min(height[i], height[j]);20 int kuan=j-i;21 int tempArea=kuan*minHeight;22 if(tempArea>maxArea)23 maxArea=tempArea;24 }25 }26 return maxArea;27 }28 29 }
这种情况直接超时，之后根据题目性质可以采取一种线性复杂度的方法
1.首先假设我们找到能取最大容积的纵线为 i , j (假定i<j)，那么得到的最大容积 C = min( ai , aj ) * ( j- i) ；
2.下面我们看这么一条性质：
①: 在 j 的右端没有一条线会比它高！ 假设存在 k |( j<k && ak > aj) ，那么 由 ak> aj，所以 min( ai,aj, ak) =min(ai,aj) ，所以由i, k构成的容器的容积C‘ = min(ai,aj ) * ( k-i) > C，与C是最值矛盾，所以得证j的后边不会有比它还高的线；
②:同理，在i的左边也不会有比它高的线；
这说明什么呢？如果我们目前得到的候选： 设为 x, y两条线（x< y)，那么能够得到比它更大容积的新的两条边必然在 [x,y]区间内并且 ax‘ > =ax , ay‘>= ay;
3.所以我们从两头向中间靠拢，同时更新候选值；在收缩区间的时候优先从 x, y中较小的边开始收缩；
从两头开始，逐渐收缩
1 package Container.With.Most.Water; 2 3 public class ContainerWithMostWater1 { 4 5 /** 6 * @param args 7 */ 8 public static void main(String[] args) { 9 // TODO Auto-generated method stub10 int height[]={1,2,3,4};11 int maxArea=maxArea(height);12 System.out.println(maxArea); 13 }14 public static int maxArea(int[] height) {15 int maxArea=0;16 int i=0;17 int j=height.length-1;18 while(i!=j){19 int tempArea=(j-i)*Math.min(height[i], height[j]);20 if(tempArea>maxArea)21 {22 maxArea=tempArea;23 }24 if(height[i]<height[j]){25 i++;26 }else{27 j--;28 }29 }30 return maxArea;31 }32 }
Leetcode Container With Most Water