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

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

总结

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