LeetCode 011. 盛最多水的容器 - 双指针与几何直觉详解

题目描述：给定一个非负整数数组 height，其中每个元素表示坐标 i 处垂直线段的高度。选择两条线段 i 和 j（i < j），与 x 轴共同组成一个容器，其能容纳的水量为 min(height[i], height[j]) × (j - i)。请返回可以容纳的最大水量。原题链接：https://leetcode.cn/problems/container-with-most-water/难度等

3Cloudream

231人浏览 · 2025-09-10 12:03:10

3Cloudream · 2025-09-10 12:03:10 发布

一、文章标题 LeetCode 011. 盛最多水的容器 - 双指针与几何直觉详解

二、文章内容

1. 题目概述

题目描述：给定一个非负整数数组 height，其中每个元素表示坐标 i 处垂直线段的高度。选择两条线段 i 和 j（i < j），与 x 轴共同组成一个容器，其能容纳的水量为 min(height[i], height[j]) × (j - i)。请返回可以容纳的最大水量。
原题链接：https://leetcode.cn/problems/container-with-most-water/
难度等级：Medium
相关标签：数组、双指针、贪心、数学、几何直觉

2. 文章目录

问题分析：
- 输入：数组 height，长度 n ≥ 2，元素为非负整数。
- 输出：两条线段与 x 轴组成容器的最大容量（整数）。
核心难点：
- 如何在 O(n) 或 O(n log n) 内找到最优的两条线，而不是 O(n^2) 穷举。
- 为什么“双指针移动短板”一定不会错过最优解（需要几何直觉或反证思想）。
解题方向（从暴力到优化）：
1. 暴力枚举所有二元组 (i, j) 计算面积，时间 O(n^2)。
2. 双指针从两端出发，每次移动较短的那一侧，时间 O(n)、空间 O(1)，工程与面试最优。

4. 算法详解

解法一：暴力枚举

算法原理

穷举所有下标对 (i, j)，i < j，计算面积 area = min(h[i], h[j]) × (j - i)，维护最大值。
适用场景：数据规模较小，或用于和优化方案的对比、验证正确性。

具体实现

步骤1：双重循环枚举所有 i、j（i < j）。
步骤2：计算每个二元组的容积并更新答案。
步骤3：返回最大值。

复杂度分析

时间复杂度：O(n^2)，两层循环枚举所有配对。
空间复杂度：O(1)，仅常数额外变量。

Java代码实现

class SolutionBruteForce {
    public int maxArea(int[] height) {
        // 边界处理：若数组为空或长度不足两条线，则无法装水
        if (height == null || height.length < 2) {
            return 0; // 使用返回值处理边界情况
        }
        int n = height.length;
        int ans = 0; // 记录最大容积
        // 枚举所有二元组 (i, j)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int h = Math.min(height[i], height[j]); // 容器有效高度由短板决定
                int w = j - i; // 宽度为下标距离
                int area = h * w;
                if (area > ans) {
                    ans = area; // 更新最大值
                }
            }
        }
        return ans;
    }
}

解法二：双指针（移动短板）

算法原理

初始化左右指针 i=0、j=n-1，面积为 min(h[i], h[j]) × (j-i)。
核心策略：每次移动较短的那一侧（短板）。
- 直觉：宽度缩小一格是必然的，想要面积增大，只能指望“高度”增大。
- 若移动长板，高度的下限仍由短板决定，且宽度变小，面积不可能增大。
- 因此只移动短板才有机会增大 min(h[i], h[j])，从而得到更大面积。
该策略可用反证法证明不会错失最优解：若最优解使用了当前短板位置，则向内移动长板不可能获得更大面积；若最优解不使用当前短板位置，则必须跨过该短板，移动短板是必要步骤。

具体实现

步骤1：i 指向最左，j 指向最右，ans=0。
步骤2：循环计算当前面积并更新答案；根据 h[i] 与 h[j] 的比较移动短板。
步骤3：当 i ≥ j 时结束循环，返回 ans。

复杂度分析

时间复杂度：O(n)，左右指针各最多移动 n 次。
空间复杂度：O(1)，仅常数额外空间。

Java代码实现

class SolutionTwoPointers {
    public int maxArea(int[] height) {
        // 边界处理：不足两条线无法形成容器
        if (height == null || height.length < 2) {
            return 0; // 使用返回值处理边界情况
        }
        int i = 0; // 左指针
        int j = height.length - 1; // 右指针
        int ans = 0; // 记录最大容积

        while (i < j) {
            // 以当前左右边界计算面积
            int h = Math.min(height[i], height[j]);
            int w = j - i;
            int area = h * w;
            if (area > ans) {
                ans = area; // 更新最大值
            }
            // 移动短板：只有抬高短板，面积才有可能变大
            if (height[i] <= height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }
}

5. 解法对比与总结

| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | 适用场景 | |------------|------------|------------|----------------------|------------------|--------------------------| | 暴力枚举 | O(n^2) | O(1) | 思路直接、易于实现 | 效率低，n 大则超时 | 仅用于小规模或正确性校验 | | 双指针 | O(n) | O(1) | 线性时间、空间最优 | 需理解正确性证明 | 面试与工程通用首选 |

最优解推荐：综合时间、空间与可读性，强烈推荐“双指针（移动短板）”解法，O(n) 时间、O(1) 空间，代码简洁可靠。

三、文章标签算法,数组,LeetCode,中等,双指针,贪心,Java

四、文章简述典型数组双指针题。本文从暴力枚举到线性双指针系统讲解盛最多水的容器，给出数学直觉与证明思路，掌握“移动短板”原则与边界处理。适合面试准备与算法入门进阶读者阅读。