11 Container With Most Water的数学证

2018-09-29 本文已影响0人 kid551

11. Container with most water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

网上给出的最优算法都比较类似，其基本想法是：将挑选的两条边分别从两端 $a_0, a_n$ 开始向中间移动，每一次只能移动两条边中的一条。每次移动的标准是将较小的那条边往中间移动一格。如果移动后的面积有所增长，则将面积最大值更新。当两条边相遇时，则停止。

网上几乎都只有这个算法的描述，而没有提供一个严格的数学证明。和好友Meiyf讨论后，整理出这个算法的数学证明。

考虑分布在左右两边的移动指标 $a_l, a_r$ ，它们分别从两端 $a_0, a_n$ 开始，通过 $a_l$ 右移、 $a_r$ 左移的方式，来搜索最优解。

假设最优解为 $a_i, a_j$ ，则我们有： $0 \leq i < j \leq n$ 。根据算法的移动方式，总是可以通过“ $a_l$ 从 $a_0$ 右移、 $a_r$ 从 $a_n$ 左移”若干步的方式，到达 $a_i, a_j$ 。

由于算法每一次只能移动一步（即 $a_l$ 右移一步或 $a_r$ 左移一步），所以两种情况：

$a_l$ 先到达 $a_i$
$a_r$ 先到达 $a_j$

必然有一种先发生。不妨假设 $a_l$ 先到达 $a_i$ （那么此时， $a_r$ 也就还未通过左移到达 $a_j$ ，它还在 $a_j$ 的右侧）。那么，我们只需证明：

在现有的算法下，后续的更新步骤都只能是： $a_r$ 不断左移、直到到达 $a_j$ 。

我们可以通过反证法来证明上述结论。

令函数 $h(a_t)$ 表示点 $a_t$ 对应的线段长度，令 $w(a_s, a_t)$ 表示点 $a_s$ 和 $a_t$ 构成的线段长度。

若假设不成立，则存在某一步：在 $a_r$ 还未通过左移到达 $a_j$ 时，停留在 $a_i$ 的 $a_l$ 需要右移一步。

下面我们来证明不可能出现上面这种情况。

若上述发生，则我们有以下结论：

$l = i < j < r$
$h(a_i) = h(a_l) < h(a_r)$ 。因为根据算法，只有长度更小的那一条边才能向中间移动。所以，只有当 $h(a_l)$ 小于 $h(a_r)$ 时，才可能出现 $a_l$ 右移。

由此，我们可以得到由 $a_i, a_r$ 两条边形成的面积为： $S^* = h(a_i) * w(a_i, a_r).$

这里的高度之所以取为 $h(a_i)$ ，是因为上面第2条已经说明了 $h(a_i)$ 比 $h(a_r)$ 小。

而此时，因为第1条已经说明 $j < r$ ，所以 $w(a_i, a_r) > w(a_i, a_j)$ 。所以我们有：

$S^* = h(a_i) * w(a_i, a_r) > h(a_i) * w(a_i, a_j) \geq \min{\{h(a_i), h(a_j)\}} * w(a_i, a_j) = S_{max}$

矛盾。所以假设命题不成立，进而当 $a_l$ 到达 $a_i$ 后，后续的所有更新步骤都只能是 $a_r$ 不断左移、直到到达 $a_j$ 。

所以，在这样的算法之下，一定能够到找到面积的最优解 $S_{max}$ 。

上一篇下一篇

猜你喜欢

热点阅读