算法解析：盛最多水的容器 —— 双指针法的高效应用

算法解析：盛最多水的容器——双指针法的高效应用

在数组相关的算法题中，“盛最多水的容器”是一道经典题目，核心考察对“优化时间复杂度”的理解。题目看似需要暴力遍历所有可能的容器组合，但通过“双指针法”可将时间复杂度从 O(n²) 降至 O(n)，大幅提升效率。本文将从题目分析入手，详解双指针法的原理、代码实现及边界情况处理，帮助彻底掌握这一解题思路。

一、题目理解：容器的水量如何计算？

首先需明确题目中的“容器”定义与水量计算逻辑，避免理解偏差：

• 容器构成：由数组中两条不同的垂线（第 i 条垂线高度为 height[i]，底部在 x 轴上）和 x 轴共同围成，形状为“矩形”（或“直角梯形”，但水量由最短边决定，本质按矩形计算）；
• 水量计算：容器的容量 = 底边长 × 高度，其中：
  • 底边长：两条垂线在 x 轴上的距离（即两个索引的差值 j - i，假设 j > i）；
  • 高度：两条垂线中较短的那条的高度（因为水无法超过较短边，否则会溢出，即 min(height[i], height[j])）；
• 目标：在所有可能的两条垂线组合中，找到容量最大的组合，返回最大容量值。

示例验证

以题目中的示例 1 为例：

• 输入数组：[1,8,6,2,5,4,8,3,7]
• 最优组合：索引 1（高度 8）和索引 8（高度 7）
• 计算过程：底边长 = 8 - 1 = 7，高度 = min(8,7) = 7，容量 = 7×7 = 49，与示例输出一致。

二、解题思路：从暴力到双指针的优化

1. 暴力解法（不推荐）

最直观的思路是“遍历所有可能的两条垂线组合”，计算每个组合的容量并记录最大值。但这种方法的时间复杂度为 O(n²)（n 为数组长度），当 n 较大（如 n=10⁴）时，会因计算量过大导致超时。

暴力解法代码（仅作对比）

class Solution {
    function maxArea($height) {
        $n = count($height);
        $maxCapacity = 0;
        // 遍历所有 i < j 的组合
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) {
                // 计算当前组合的容量
                $width = $j - $i;
                $currentHeight = min($height[$i], $height[$j]);
                $capacity = $width * $currentHeight;
                // 更新最大容量
                $maxCapacity = max($maxCapacity, $capacity);
            }
        }
        return $maxCapacity;
    }
}

2. 双指针法（推荐，O(n) 时间复杂度）

双指针法的核心是“通过贪心策略，每次排除不可能成为最优解的组合，逐步缩小搜索范围”。具体思路如下：

1. 初始化指针：左指针 l 指向数组起始（索引 0），右指针 r 指向数组末尾（索引 n-1）；
2. 计算当前容量：以 l 和 r 为边界，计算当前容器的容量，更新最大容量值；
3. 移动指针的关键逻辑：
   • 若 height[l] < height[r]：此时容器的高度由 height[l] 决定（较短边）。若向右移动右指针 r，底边长会减小，而高度最多仍为 height[l]（甚至更小），容量必然减小——因此，左指针 l 向右移动（尝试寻找更长的左边，可能提升容量）；
   • 若 height[l] >= height[r]：同理，容器高度由 height[r] 决定，向左移动左指针 l 会导致容量减小——因此，右指针 r 向左移动；
4. 终止条件：当左指针 l 与右指针 r 相遇（l >= r）时，遍历结束，此时记录的最大容量即为答案。

双指针法的正确性证明

为什么这种“移动较短边指针”的策略能找到最优解？

• 假设当前左指针 l 对应的高度 < 右指针 r 对应的高度，此时以 l 为左边的所有组合中，l 与 r 的组合是容量最大的（因为其他右指针 j < r 会导致底边长更小，高度不会超过 height[l]）；
• 因此，以 l 为左边的所有组合无需再考虑，直接移动 l 即可——通过这种方式，每次移动指针都排除了一组“不可能是最优解”的组合，最终只需遍历一次数组，时间复杂度降至 O(n)。

三、完整代码实现（PHP）

结合双指针法的思路，实现代码如下，代码简洁且注释清晰，覆盖所有核心逻辑：

class Solution {
    /**
     * @param Integer[] $height 存储各垂线高度的数组
     * @return Integer 最大容器容量
     */
    function maxArea($height) {
        $n = count($height);
        if ($n < 2) {
            return 0; // 边界情况：至少需要两条垂线才能构成容器
        }
        
        $left = 0;          // 左指针：初始指向数组开头
        $right = $n - 1;    // 右指针：初始指向数组结尾
        $maxCapacity = 0;   // 记录最大容量，初始为 0
        
        // 循环：左指针 < 右指针时，持续搜索
        while ($left < $right) {
            // 1. 计算当前指针组合的容量
            $width = $right - $left;                          // 底边长 = 右指针索引 - 左指针索引
            $currentMinHeight = min($height[$left], $height[$right]); // 高度 = 较短边的高度
            $currentCapacity = $width * $currentMinHeight;    // 当前容量 = 底边长 × 高度
            
            // 2. 更新最大容量（若当前容量更大，则覆盖）
            if ($currentCapacity > $maxCapacity) {
                $maxCapacity = $currentCapacity;
            }
            
            // 3. 移动指针：始终移动较短边的指针，排除无效组合
            if ($height[$left] < $height[$right]) {
                $left++;  // 左边更短，左指针右移，寻找更长的左边
            } else {
                $right--; // 右边更短（或相等），右指针左移，寻找更长的右边
            }
        }
        
        return $maxCapacity; // 返回最终的最大容量
    }
}

四、边界情况与测试验证

1. 常见边界情况

• 数组长度为 2：如示例 2 输入 [1,1]，此时只有一种组合，容量 = 1×(1-0) = 1，代码返回正确；
• 数组元素单调递增/递减：如输入 [1,2,3,4,5]，最优组合为索引 0（1）和 4（5），容量 = 4×1 = 4；输入 [5,4,3,2,1]，最优组合同样为索引 0（5）和 4（1），容量 = 4×1 = 4；
• 数组中有相等的元素：如输入 [2,3,4,5,5,4,3,2]，最优组合为索引 0（2）和 7（2），容量 = 7×2 = 14，代码会正确处理（指针移动时，相等情况下移动任意一边均可，不影响最终结果）。

2. 测试用例运行

测试用例 1

• 输入：[1,8,6,2,5,4,8,3,7]
• 运行过程：
  • 初始 left=0（1）、right=8（7），容量 = 8×1 = 8 → 最大容量=8；
  • 左边更短，left=1（8），此时容量 = 7×7 = 49 → 最大容量=49；
  • 右边更短（7 < 8），right=7（3），容量 = 6×3 = 18 → 不更新；
  • 右边更短（3 < 8），right=6（8），容量 = 5×8 = 40 → 不更新；
  • 两边相等（8=8），right=5（4），容量 = 4×4 = 16 → 不更新；
  • 后续继续移动指针，容量均小于 49，最终返回 49。

测试用例 2

• 输入：[1,1]
• 运行过程：
  • left=0、right=1，容量 = 1×1 = 1 → 最大容量=1；
  • 两边相等，right=0，循环终止，返回 1。

五、总结

“盛最多水的容器”问题的核心是双指针法的贪心应用：通过“移动较短边指针”排除无效组合，在 O(n) 时间内找到最优解。解题时需注意：

1. 明确容量计算逻辑（底边长 × 较短边高度）；
2. 理解指针移动的本质（排除不可能成为最优解的组合）；
3. 处理边界情况（数组长度 < 2 时返回 0）。

这种“通过贪心策略缩小搜索范围”的思路，也适用于其他数组优化问题（如“三数之和”“接雨水”等），掌握后可举一反三，提升算法解题效率。