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.
解法：
最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到指针重合为止就行了。
public class Solution {
public int maxArea(int[] height) {
int max = 0;
int i = 0;
int j = height.length - 1;
while (i < j) {
int lower = Math.min(height[i], height[j]);
max = Math.max(lower * (j - i), max);
if (height[i] < height[j]) i++;
else j--;
}
return max;
}
}
改进：如果较短的边向中间移动后，新的边比原来的短，可以直接跳过，找下一条边，减少一些计算量。
public class Solution {
public int maxArea(int[] height) {
int max = 0;
int i = 0;
int j = height.length - 1;
while (i < j) {
int lower = Math.min(height[i], height[j]);
max = Math.max(lower * (j - i), max);
if (height[i] < height[j])
while (i < j && height[i] <= lower) i++;
else
while (i < j && height[j] <= lower) j--;
}
return max;
}
}