盛水最多的容器

题目描述

给定一个长度为 n 的整数数组 height，每个元素代表一条垂直线的高度，横坐标位置为下标 i（从 0 开始）。请找出两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，并返回该最大水量。

形式化定义： 对于任意 0 <= i < j < n，容器盛水量为：

area = min(height[i], height[j]) * (j - i)

求所有 (i, j) 中 area 的最大值。

示例：

输入：height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
输出：49
解释：选择下标 1 和 8（高度 8 和 7），宽度为 7，面积为 min(8,7)*7 = 49。

约束条件：

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

解题思路

暴力枚举（基础）

• 思想：使用两层循环枚举所有可能的左右边界组合 (i, j)（i < j），计算面积并更新最大值。
• 优点：逻辑直观，易于实现。
• 缺点：时间复杂度 O(n²)，数据量大时不可用。

双指针法（最优）

• 思想：初始化左指针 left = 0，右指针 right = n-1。每次计算当前面积并更新最大值，然后移动指向高度较小的指针向中心靠拢。
• 正确性依据：宽度减小，若移动长板，高度不会增加（短板不变或减小），面积只会减少；只有移动短板，才可能找到更高的短板，从而有机会增大面积。因此移动短板指针不会遗漏最优解。
• 复杂度：O(n) 时间，O(1) 空间。

伪代码

暴力枚举

function maxArea_brute(height):
    n = length(height)
    max_area = 0
    for i = 0 to n-2:
        for j = i+1 to n-1:
            area = min(height[i], height[j]) * (j - i)
            max_area = max(max_area, area)
    return max_area

双指针法

function maxArea_twoPointer(height):
    left = 0
    right = length(height) - 1
    max_area = 0
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        area = h * width
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left = left + 1
        else:
            right = right - 1
    return max_area

流程图（双指针法）

代码实现

C 语言

暴力枚举版本

#include <stdio.h>

int maxArea_brute(int* height, int heightSize) {
    int max_area = 0;
    for (int i = 0; i < heightSize - 1; i++) {
        for (int j = i + 1; j < heightSize; j++) {
            int h = height[i] < height[j] ? height[i] : height[j];
            int area = h * (j - i);
            if (area > max_area) max_area = area;
        }
    }
    return max_area;
}

int main() {
    int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int size = sizeof(height) / sizeof(height[0]);
    printf("暴力法结果: %d\n", maxArea_brute(height, size)); // 49
    return 0;
}

双指针版本

#include <stdio.h>

int maxArea_twoPointer(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int max_area = 0;
    while (left < right) {
        int width = right - left;
        int h = height[left] < height[right] ? height[left] : height[right];
        int area = h * width;
        if (area > max_area) max_area = area;
        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return max_area;
}

int main() {
    int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int size = sizeof(height) / sizeof(height[0]);
    printf("双指针法结果: %d\n", maxArea_twoPointer(height, size)); // 49
    return 0;
}

Java 语言

暴力枚举版本

public class Solution {
    public int maxArea_brute(int[] height) {
        int maxArea = 0;
        int n = height.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int h = Math.min(height[i], height[j]);
                int area = h * (j - i);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("暴力法结果: " + sol.maxArea_brute(height)); // 49
    }
}

双指针版本

public class Solution {
    public int maxArea_twoPointer(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int width = right - left;
            int h = Math.min(height[left], height[right]);
            int area = h * width;
            maxArea = Math.max(maxArea, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("双指针法结果: " + sol.maxArea_twoPointer(height)); // 49
    }
}

输出示例

对于输入 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]，两种方法均输出：

最大盛水量: 49

复杂度分析

| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 | | -------- | ---------- | ---------- | --------------------- | | 暴力枚举 | O(n²) | O(1) | 小数据量（n < 1000） | | 双指针法 | O(n) | O(1) | 大数据量（n ≤ 10^5） |

• 双指针法：每个元素最多被访问一次，常数级额外空间，为最优解法。

总结

• 暴力法思路直观，适合理解问题，但效率不足以应对大规模输入。
• 双指针法利用“短板效应”，通过每次移动较短的指针，在 O(n) 时间内找到最优解，是本题的标准解法。
• 核心要点：面积由宽度和短板高度共同决定，当宽度缩小时，只有提高短板高度才能增加面积，因此移动长板无意义。
• 掌握双指针思想有助于解决许多数组区间最值类问题（如“接雨水”、“三数之和”等）。