[LeetCode]-011-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(n^2))

 public int maxArea(int[] height) {
     int area = 0;
     int min = 0;
     for(int i=0; i<height.length; i++){
         for(int j=i+1; j<height.length; j++){
             if(height[i] == height[j])
                 area = Math.max(area, height[i]*(j-i));
             else{
                 min = Math.min(height[i],height[j]);
                 area = Math.max(area, min*(j-i));
             }
         }
     }
     return area;
 }

第二种方法：

 public int maxArea(int[] height) {
         int area = 0;
         int begin = 0;
         int end = height.length-1;
         while(begin<end){
             area = Math.max(area, (end-begin)*Math.min(height[begin],height[end]));
             if(height[begin]<height[end])
                 begin++;
             else
                 end--;
         }
         return area;
     }