第11题 盛最多水的容器
题目
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
注意：你不能倾斜容器，n 至少是2。
题目地址：https://leetcode-cn.com/problems/container-with-most-water/description/
问题分析
这道题目其实就是求在笛卡尔坐标系中，有若干条垂直于X轴的垂直线，每隔1个单位有一条垂直线，如果两条垂直线和X轴可以构成一个容器的话，求这个容器最多可盛多少水。
这题一看没什么头绪，自己也是思考了很久。下面分析其中的规律，根据这个规律可将时间复杂度降低到线性。
规律
假设容器的左端位于left位置，容器的右端位于right位置(left < right)，容器的容积为S[left,right]，且容器左端比右端底，也即height[left] < height[right]，
那么如果将容器右端向左靠拢，此时容器的容积S[left,right-n]一定是缩小的：
S[left,right] > S[left,right-n] n>=1 (规律)
于是我们可以得出结论，要想让容器的容积变大，根据刚才的规律可知我们没有必要将容器的右端向左端靠拢，而是将容器的左端向右端靠拢，求最大值
S = max(S[left,right],S[left+1,right])
左端不断地靠拢右端，不断地求最大值，直到height[left] > height[right] 时改换右端向左端靠拢，或者直到left与right相遇结束
于是问题就和双指针求解a+b=0一样了，每次都只需要移动一端的指针向另一端靠拢求最大值，移动哪一端的话考虑上面的规律，直到两个指针相遇结束。
代码
public int maxArea(int[] height) {
if(height == null || height.length == 2){
return height[0] > height[1] ? height[1] : height[0];
}
int left = 0;
int right = height.length -1;
int max = (height.length - 1) * (height[left] > height[right] ? height[right]:height[left]);
while(left < right){
int l = height[left];
int r = height[right];
if(l > r){
//缩小右边的
right--;
int newV = getV(height[left],height[right],left,right);
max = Math.max(newV,max);
}else{
//缩小左边的
left++;
int newV = getV(height[left],height[right],left,right);
max = Math.max(newV,max);
}
}
return max;
}
/**
* 获取面积
* @return
*/
public static int getV(int leftHeight,int rightHeight,int left,int right){
return (right - left )*(leftHeight > rightHeight?rightHeight:leftHeight);
}
