问题描述：
给定n个非负的整数 a1, a2, ..., an , 其中每一个代表坐标系 (i, ai)中的一个点. 画出n条竖线，每条线的起点和终点分别为 (i, ai) 和 (i, 0). 找到其中的两条线，它们和x轴一起组成一个容器使得该容器装水最多。
PS: 容器不会倾斜，并且n最小是2。
上图中的竖线由数组 [1,8,6,2,5,4,8,3,7]给出。 在这个实例中，最大蓄水量容器 (蓝色区域)可蓄水容量是49 .png
示例：
输入： [1,8,6,2,5,4,8,3,7]
输出： 49
一般解法
最容易想到的便是暴力法，针对每条竖线计算其和其前方所有竖线组成的容器蓄水量，最终得到这些竖线组成的所有容器中的最大值。
时间复杂度：
计算次数为=
，从而时间复杂度为
。
代码实现
private static int solutionV1(int[] height) {
if (height == null || height.length <= 1) {
return 0;
}
int maxArea = Integer.MIN_VALUE;
int curArea;
for (int i = 1; i < height.length; i++) {
for (int j = i - 1; j >= 0; j--) {
curArea = Math.min(height[i], height[j]) * (i - j);
if (maxArea < curArea) {
maxArea = curArea;
}
}
}
return maxArea;
}
进阶解法
一般解法的时间复杂度为，如果要优化的话，我们需要找到更低阶的解法，比如
。
通过观察可以发现，对于任意的，如果
，那么有:
所以对任意的k，，也就是说在所有包含i的容器中最大的就是
。
令，那么
。
同理，如果，那么就有：
令，那么
。
从上述的推理我们可以看出，如果，我们便可以直接把i右移，否则把j左移，从而去掉一些不必要的计算，这样便可以在
时间内得到结果。
代码实现
private static int solutionV2(int[] height) {
if (height == null || height.length <= 1) {
return 0;
}
int maxArea = 0;
int curArea;
int s = 0, e = height.length - 1;
while (s < e) {
curArea = height[s] < height[e] ? (e - s) * height[s] : (e - s) * height[e];
maxArea = maxArea > curArea ? maxArea : curArea;
if (height[s] < height[e]) {
s++;
} else {
e--;
}
}
return maxArea;
}
总结
该题是典型的需要通过数学推理才能找到更优解法的题型，十分有趣，特此整理纪念。
