盛水最多的容器

题目描述

给你 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，每个数代表坐标中的一个点 $(i, a_i)$。在坐标内画出 $n$ 条垂直线，垂直线 $i$ 的两个端点 $(i, a_i)$ 和 $(i, 0)$。找出其中的两条线，使得它们与 $x$ 轴共同构成容器可以容纳最多的水。

说明：不能倾斜容器。

例如，给定如下非负整数 $[1, 8, 6, 2, 5, 4, 8, 3, 7]$

如图两条红色线形成的蓝色区域能够盛放最多的水，其值为 $7*7=49$。

解题思路

最简单的思路就是遍历所有柱之间能够容纳多少流量，然后取最大值

public int maxArea(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length - 1; i++) {
        for (int j = i + 1; j < height.length; j++) {
            max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
        }
    }
    
    return max;
}

现在我们考虑一个更快的算法。我们考虑范围 $[i, j]$ 之间的柱子能够容纳多少水量。首先考虑边界的两个柱子 $(i, a_i)$ 与 $(j, a_j)$ 之间能够容纳多少水量，我们不妨假设 $a_i \leq a_j$，那么它们之间能够容纳的水为
$$
a_i * (j - i)
$$
那么对于任何 $i < k < j$，我们可以确定柱 $(i, a_i)$ 与柱 $(k, a_k)$ 能够容纳的水量一定小于 $a_i * (j - i)$。因为

$x$ 与 $a_k$ 之间最短的边为 $\min ( a_i, a_k ) \leq a_i$
因为$i < k < j$，所以 $k - i < j - i$

所以 $(i, x)$ 与$(k ,a_k)$ 能够包含的水量
$$
\min ( a_i, a_k ) * (k - i) < a_i * (j - i)
$$
因为找的是能够容纳最大的水量，我们不必考虑 $(i, a_i)$ 与其他柱的配对了，这样可以减少很多的计算量。

将上面的想法转化为算法步骤，我们的目的是计算范围 $[0, length-1]$ 之间的柱子能够容纳多少水量，初始令 i = 0, j = length -1。算法过程为，当我们来到$(i, a_i)$ 与 $(j, a_j)$ 两个柱时：

首先计算它们能够容纳多少水量，如果大于目前的最大值，则更新最大值，否则不更新最大值
如果 $a_i \leq a_j$，那么不必计算柱 $(i, a_i)$ 与其他柱的配对，执行 i++
如果 $a_i > a_j$，那么不必计算 $(j, a_j)$ 与其他柱的配对，执行 j--

当 $i \geq j$ 时，算法执行结束，此时的最大值即为能够容纳的最大水量。

public int maxArea(int[] height) {

    int start = 0;
    int end = height.length - 1;

    int max= 0;
    
    while (start < end) {
        // 计算两个柱之间能够容纳的水量，如果大于最大值，则更新最大值
        int s = (end - start) * Math.min(height[start], height[end]);
        if (max < s) {
            max = s;
        }
        // 如果 a_i <= a_j，则 i++，否则 j--
        if (height[start] <= height[end]) {
            start++;
        } else {
            end--;
        }
    }
    return max;
}