LeetCode之蓄水量最大的容器（Container With Most Water）

问题描述：
给定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

一般解法

最容易想到的便是暴力法，针对每条竖线计算其和其前方所有竖线组成的容器蓄水量，最终得到这些竖线组成的所有容器中的最大值。
时间复杂度：
计算次数为 $\sum_{i=1}^ni$ = ${n(n-1)\over 2}$ ，从而时间复杂度为 $O(n^2)$ 。
代码实现

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;
}

进阶解法

一般解法的时间复杂度为 $O(n^2)$ ，如果要优化的话，我们需要找到更低阶的解法，比如 $O(n)$ 。
通过观察可以发现，对于任意的 $i，j(0 =< i < k < j< n)$ ，如果 $h_i<=h_j$ ，那么有:
$area(i, j)=min(h_i, h_j) * (j - i)=h_i*(j-i)>h_i*(j-k)>=min(h_i, h_k)(k-i)=area(i,k)$
所以对任意的k， $area(i,j)>area(i,k)$ ，也就是说在所有包含i的容器中最大的就是 $area(i,j)$ 。
令 $area(i,j)=max_{i,j}$ ，那么 $maxArea=max(area(i+1,j),max_{i,j})$ 。
同理，如果 $h_i>h_j$ ，那么就有：
令 $area(i,j)=max_{i,j}$ ，那么 $maxArea=max(area(i,j-1),max_{i,j})$ 。
从上述的推理我们可以看出，如果 $h_i<=h_j$ ，我们便可以直接把i右移，否则把j左移，从而去掉一些不必要的计算，这样便可以在 $O(n)$ 时间内得到结果。
代码实现

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;
}

总结

该题是典型的需要通过数学推理才能找到更优解法的题型，十分有趣，特此整理纪念。