leetcode-11-java

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.

/**
    * 时间复杂度0(n^2)
    * @param height
    * @return
    */
   public static int maxAreaN2(int[] height) {
       int maxArea = 0;
       for (int i = 0; i < height.length; i++) {

           for (int j = i + 1; j < height.length; j++) {
               //取最小的高度
               int maxHeight = height[i] < height[j] ? height[i] : height[j];

               int tmpArea = maxHeight * (j - i);
               maxArea = maxArea < tmpArea ? tmpArea : maxArea;
           }
       }
       return maxArea;
   }


   /**
    * 时间复杂度0(n)
    * @param height
    * @return
    */
   public static int maxAreaN(int[] height) {
       int left = 0;
       int right = height.length - 1;

       int maxArea = 0;
       while (left < right) {
           int tmp = Math.min(height[left], height[right]) * (right - left);
           maxArea = Math.max(maxArea, tmp);

           if (height[left] < height[right]) {
               left ++;
           } else {
               right --;
           }
       }

       return maxArea;
   }