日野弥生：勉強しよう

LeetCode 11 - 盛最多水的容器

发表于2025年04月18日

整体思路一般都能想到是从首尾两端向中间逼近求解。但是由于逼近的过程中，具体是左指针动还是右指针动，涉及到贪心的理念和数学证明。不过，结论基本和体感差不多，每次选择长板留下。

不过这个解法为什么正确，为什么双指针往中间移动时，不会漏掉某些情况呢？

双指针法正确性证明

以 i, j 表示前后指针，H[i] 表示位置 i 处的高度，n 是输入的数据长度。S(i, j) = min(H[i], H[j]) * (j - i) 是 (i, j) 对的面积。

最大性证明

根据双指针法的求解过程，可以很容易得到一个性质：

H[i] 与 H[j] 中至少有一个是在 (0, i] 和 [j, n-1) 中，H 的最大值。

反证法证明：

将 (0, i) 与 (j, n-1) 称为已知区域，[i, j] 中间所有序偶对称为未知区域。

假设已知区域有 H[k] 为最大值，比 H[i] 和 H[j] 都大。那么很明显，算法执行到 k 之后，将不可能获得移动机会，算法不可能移动到 [i, j] 状态。因此假设不成立。

安全性证明

深入思考，移动较小指针到底意味着什么？

每移动一次较小指针，意味着计算了一对 S(i, j) 的值，而消去了一排 S(i, k), i < k <= j。我们定义移动指针的安全性：
如果一次移动指针，消去的所有 (i, j) 对，要么是被计算过，要么是可证明小于某个已计算过的 S(i, j)，那么我们可以说这一次指针移动是安全的。

以初始状态为例：

(i, j) = (0, n - 1)，那么该状态将计算 S(0, n - 1)。

• 如果 H[0] < H[n - 1]，那么将消去 (0, 1), (0, 2), ..., (0, n) 等 n - 1 个状态。
• 如果 H[0] > H[n - 1]，那么将消去 (0, n - 1), (1, n - 1), ..., (n - 2, n - 1) 等 n - 1 个状态。

定义消去集为 X，待解集 R，R_i = R_{i-1} - X。

证明

1. 算法的初始状态是安全的

算法的初始状态，待解集合 R = {(i, j), 0 <= i < j <= n - 1}，而正确状态一定位于 R 中。因此，初始状态是安全的。

2. 若第 k 个状态是安全的，那么完成移动小指针操作得到的第 k+1 个状态也是安全的

从状态 k 到状态 k+1，算法完成了一次消去操作。

• 当 H[i] < H[j] 时，完成的是消去 X = {(i, i + 1), (i, i + 2), ..., (i, j)}。

对于任意 (i, j') ∈ X，我们有：

• 如果 H[i] < H[j']，那么 S(i, j') = H[i] * (j' - i) < H[i] * (j - i) = S(i, j)，所以 X 中的状态都小于 S(i, j)。
• 如果 H[i] >= H[j']，那么 S(i, j') = H[j'] * (j' - i) <= H[i] * (j' - i) < H[i] * (j - i) = S(i, j)，所以 X 中的状态都小于 S(i, j)。

因此，当 H[i] < H[j] 时，从 R 中消去 X 集合是安全的。

• 如果 H[i] >= H[j]，其实是与情形 1 对称的，边界等于归到任意一边不影响。
  设 X = (i, j), (i + 1, j), ..., (j - 1, j)。考虑 (i', j)：

  • 如果 H[i'] < H[j]，那么 S(i', j) = H[i'] * (j - i') < H[j] * (j - i') < H[j] * (j - i) = S(i, j)。
  • 如果 H[i'] >= H[j]，那么 S(i', j) = H[j] * (j - i') < H[j] * (j - i) = S(i, j)。

因此，当 H[i] >= H[j] 时，从 R 中消去 X 集合是安全的。

结论

由 1 和 2 可知，从 R 中消去 X 是安全的。

因此，算法的任一状态都是安全的，证明了双指针法的正确性。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        length = len(height)
        head, tail = 0, length - 1
        maximum = 0
        while head != tail:
            if height[head] < height[tail]:
                maximum = max(maximum, height[head] * (tail - head))
                head += 1
            else:
                maximum = max(maximum, height[tail] * (tail - head))
                tail -= 1
        return maximum