### 题目

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 and n is at least 2.

### 暴力遍历 O(n^2)

#### 代码

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


### 我自己的O(nlogn)动态规划算法

#### 代码

import java.util.*;

public class Solution {
public static int maxArea(int[] height) {
List<Map.Entry<Integer,Integer>> list = new ArrayList<>();
for (int i = 0; i < height.length; i++) {
}
list.sort(new Comparator<Map.Entry<Integer,Integer>>() {
public int compare(Map.Entry<Integer,Integer> entry1, Map.Entry<Integer,Integer> entry2) {
return Integer.compare(entry2.getValue(),entry1.getValue());
}
});
int theHeight = list.get(1).getValue();
int num1 = list.get(0).getKey();
int num2 = list.get(1).getKey();
int[] theRange = new int[]{Math.min(num1,num2), Math.max(num1,num2)};
int maxArea = theHeight * (theRange[1] - theRange[0]);
for (int i = 2; i < list.size(); i++) {
theHeight = list.get(i).getValue();
int newRange = list.get(i).getKey();
theRange[0] = Math.min(theRange[0],newRange);
theRange[1] = Math.max(theRange[1],newRange);
int newArea = theHeight * (theRange[1] - theRange[0]);
maxArea = Math.max(maxArea,newArea);
}
return maxArea;
}
}


### 最优算法 O(n)

In this problem, the smart scan way is to set two pointers initialized at both ends of the array. Every time move the smaller value pointer to inner array. Then after the two pointers meet, all possible max cases have been scanned and the max situation is 100% reached somewhere in the scan.

#### 代码

import java.util.*;

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