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.
题目可以这么理解，在i位置有条高为ai的竖线，让你选出两台竖线构成一个容器，使得该容器装的水最多，注意容器不能倾斜。
|
| |
| |
| | | | |
| | | | | | |
| | | | | | | | | | |
0 1 2 3 4 5 6 7 8 9 10
如上图，横纵都为一个单位，我们很容易看出来1和9位置组成的容器容积最大，所盛水为24个单位。大家都知道桶的容积是有最短的一条木板决定的，在这副二维图中是由短的一条边决定的。
没有什么问题是通过暴力解决不了的，这道题也是，我们直接暴力选取两条边，算最大容积就好了，时间复杂度O(n^2)。 显然，这并不是最优解，其实还有O(n)的解法。
我们用两个指针l和r分别从两头往中间移动，直到重合，记录下移动过程中最大的容积。 移动的策略是如果height[l] < height[r] l右移，反之r左移。 代码很简单，但是很难理解，为啥这样就算出正确答案了？？
想想看，容器的容积是有最短的一条边决定的，l和r如果你把长边向中间移动的话，容积只会减少不会增加，对不，所以移动长边是无意义的。但是移动短边，有可能短边会变长，容积可能变大。不知道我说清楚了吗，反正这就是大体的思路，很明显这是O(n)的时间复杂度。
代码如下：
public class Solution {
public int maxArea(int[] height) {
if (height.length < 2) return 0;
int ans = 0;
int l = 0;
int r = height.length - 1;
while (l < r) {
int tmp = (r - l) * Math.min(height[l], height[r]);
if (v > ans)
ans = tmp;
if (height[l] < height[r])
l++;
else r--;
}
return ans;
}
}
