如何使用Java解决盛最多水容器的问题

问题描述

盛最多水容器的问题（Container With Most Water）是一个经典的算法问题。给定一个非负整数数组 height，其中每个元素代表一个垂直线的高度。数组中的两个元素与 x 轴共同构成一个容器，容器的容量由两个垂直线之间的最小高度和它们之间的距离决定。我们的目标是找到能够盛放最多水的容器。

示例

假设我们有一个数组 height = [1,8,6,2,5,4,8,3,7]，那么最大的容器容量为 49，由高度为 8 和 7 的两条垂直线构成，它们之间的距离为 7（即数组下标为 1 和 8 的元素）。

解决思路

暴力法

最直观的解决方法是使用双重循环，遍历所有可能的垂直线对，计算每个容器的容量，并记录最大值。这种方法的时间复杂度为 O(n^2)，在数组长度较大时效率较低。

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

双指针法

为了提高效率，我们可以使用双指针法。双指针法的基本思想是从数组的两端开始，逐步向中间移动指针，每次移动高度较小的指针，以期望找到更大的容器容量。

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

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。双指针法只需要遍历数组一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

代码解释

1. 初始化指针：我们使用两个指针 left 和 right，分别指向数组的起始和末尾。
2. 计算容量：在每次循环中，计算当前指针所指向的两条垂直线构成的容器的容量，并更新最大值。
3. 移动指针：比较两条垂直线的高度，移动高度较小的指针，以期望找到更大的容量。
4. 返回结果：当 left 和 right 指针相遇时，循环结束，返回最大容量。

总结

通过使用双指针法，我们可以高效地解决盛最多水容器的问题。这种方法不仅减少了时间复杂度，还保持了较低的