问题：

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.

解决：

【注】题目的意思是，数组中的每个数对应一条线段的长度，索引对应x坐标，两个索引可以组成一个底部的宽，高度就是前面所说的线段的长度，而既然是要盛水，高度就是两个线段中较短的一个。

① 暴力解决，超时。

class Solution {

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

② 因为数组下标i是有序的，使用双指针分别从左右两端向中间移动，如果height[i] < height[j]，left左移（这时右侧的面积值可能会大于当前值），否则，right右移。

class Solution {//12ms

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

③ 进化版

public class Solution { //7ms

    public int maxArea(int[] height) {         int maxArea = 0;         int left = 0;         int right = height.length - 1;         while(left < right){             if(height[left] > height[right]){                 if(maxArea < height[right] * (right - left))                     maxArea = height[right] * (right - left);                 right --;             }else{                 if(maxArea < height[left] * (right - left))                     maxArea = height[left] * (right - left);                    left ++;             }         }         return maxArea;     } }