11. 盛最多水的容器

Bin大约 2 分钟

11. 盛最多水的容器

题目：盛最多水的容器

描述：

给定一个长度为 n 的整数数组 height，数组中的每个元素 height[i] 表示第 i 条垂线的高度。第 i 条垂线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

要求：返回容器可以储存的最大水量。

说明：你不能倾斜容器，容器的边界只能沿垂直线和水平线。

示例：

示例 1:

输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 容器可以容纳的水是由第 2 条线和第 9 条线构成的，水量为 49。

示例 2:

输入: height = [1,1]
输出: 1

解题思路：

本题使用 双指针法 来解决。我们可以用两个指针分别指向数组的两端，然后根据容器的宽度和高度来计算水量。

步骤：

初始化两个指针：左指针指向数组的起始位置 0，右指针指向数组的末尾位置 n-1。
计算当前容器的水量：水量由容器的宽度和高度决定，min(height[left], height[right]) * (right - left)。
更新最大水量：每次计算水量时，更新最大水量。
移动指针：
- 如果 height[left] 小于 height[right]，则移动左指针向右移动，因为移动较矮的指针有可能找到更大的容器。
- 如果 height[left] 大于或等于 height[right]，则移动右指针向左移动。
停止条件：当左指针和右指针相遇时停止。

通过这种方法，能够在 O(n) 的时间复杂度内找到最大水量。

代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] height = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            height[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        System.out.println(solution.maxArea(height));

        scanner.close();
    }
}

class Solution {
    public int maxArea(int[] height) {
        int left = 0;  // 左指针
        int right = height.length - 1;  // 右指针
        int maxWater = 0;  // 最大水量

        while (left < right) {
            // 计算当前容器的水量
            int currentWater = Math.min(height[left], height[right]) * (right - left);
            maxWater = Math.max(maxWater, currentWater);  // 更新最大水量

            // 移动较矮的指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxWater;
    }
}

时间复杂度分析：

时间复杂度：O(n)，其中 n 是数组的长度。我们只需要一次遍历，左右指针分别移动一次，直到两者相遇。
空间复杂度：O(1)，我们只用了常数级别的额外空间。

总结：

通过双指针法，我们可以在 O(n) 的时间内高效地解决这个问题。每次计算水量时，根据两端的高度决定移动哪个指针，从而不断逼近最优解。