题目描述

给定 $n$ 个非负整数 $a_1, a_2, … a_n$，表示平面上有 $n$ 条竖线，第 $i$ 条竖线的两个端点是 $(i, a_i)$ 和 $(i, 0)$。请找出两条竖线，使得它们与 $x$ 轴组成的容器能盛最多的水。

注意：不可以把线倾斜，并且 $n \ge 2$。

算法

(指针扫描) $O(n)$

这题的思路比较精巧，我们先给出做法，再给出证明。

做法：用两个指针 $i, j$ 分别指向首尾，如果 $a_i \gt a_j$，则 $j\-\-$；否则 $i++$，直到 $i =j$ 为止，每次迭代更新最大值。

证明：假设最优解对应的两条线的下标是 $i’, j’(i’ \lt j’)$，在 $i, j$ 不断靠近的过程中，不妨假设 $i$ 先走到 $i’$，则此时有 $j’ \lt j$。反证，如果此时 $a_i \le a_j$，设 $S$ 表示 $i, j能盛多少水$，$S’$ 表示 $i’, j’$ 能盛多少水，则：
$S = min(a_i, a_j) * (j - i)$
$= a_i * (j - i)$
$\gt a_i * (j’ - i)$
$\ge min(a_i, a_{j’}) * (j’ - i) = S’$
与 $S’$ 是最优解矛盾，因此 $a_i \gt a_j$，所以 $j$ 会一直走到 $j’$，从而得到最优解。

时间复杂度分析：两个指针总共扫描 $n$ 次，因此总时间复杂度是 $O(n)$.

C++ 代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        for (int i = 0, j = height.size() - 1; i < j; )
        {
            res = max(res, 
                min(height[i], height[j]) * (j - i));
            if (height[i] > height[j]) j -- ;
            else i ++ ;
        }
        return res;
    }
};