LeetCode 笔记系列二 Container With Most Water

题目：Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

就是说，x轴上在1,2,...,n点上有许多垂直的线段，长度依次是a₁, a₂, ..., an。找出两条线段，使他们和x抽围成的面积最大。面积公式是 Min(a_i, a_j) X |j - i|

解法1：大家都能想到的，穷举所有(i,j)可能，找一个最大的。

 1 //O(n^2)
 2      public static int maxArea(int[] height) {
 3          // Start typing your Java solution below
 4          // DO NOT write main() function
 5          int maxArea = 0;
 6          for(int i = 1; i < height.length; i++){
 7              if(height[i] == 0)continue;
 8              for(int j = 0; j < i; j++) {
 9                  int area = area(height,i,j);
10                  if(area > maxArea) {
11                      maxArea = area;
12                  }
13              }
14          }
15          return maxArea;
16      }

O(n^2)穷举

不过这样的话无法通过leetcode大集合。

解法2：可以对解法1中的第二个循环中的j做预先判断从而跳过某些情况。在我们检查比i小的各个j时，计算面积的短板不会超过a_i本身。平均到距离上，j不会在一定距离上靠近i。

 1 public static int maxArea(int[] height) {
 2          // Start typing your Java solution below
 3          // DO NOT write main() function
 4          int maxArea = 0;
 5          for(int i = 1; i < height.length; i++){
 6              if(height[i] == 0)continue;
 7              int maxPossibleIdx = i - maxArea/height[i];
 8              for(int j = 0; j < i && j <= maxPossibleIdx; j++) {
 9                  int area = area(height,i,j);
10                  if(area > maxArea) {
11                      maxArea = area;
12                  }
13              }
14          }
15          return maxArea;
16      }

O(n^2)预判断

这个方法能够通过大集合。

解法3： O(n)的复杂度。保持两个指针i,j；分别指向长度数组的首尾。如果a_i 小于a_j，则移动i向后（i++）。反之，移动j向前（j--）。如果当前的area大于了所记录的area，替换之。这个想法的基础是，如果i的长度小于j，无论如何移动j，短板在i，不可能找到比当前记录的area更大的值了，只能通过移动i来找到新的可能的更大面积。

 1 public static int maxArea(int[] height){
 2         int maxArea = 0;
 3         int i = 0;
 4         int j = height.length - 1;
 5         if(j <=0)return 0;
 6         while(i < j) {
 7             int area = area(height, i, j);
 8             if(height[i] < height[j]){
 9                 i++;
10                 
11             }else {
12                 j--;
13             }
14             if(area > maxArea) maxArea = area;
15         }
16         return maxArea;
17     }

O(n)