LeetCode11-盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

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

提示

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

分析

1. 理解问题

题目的目标是，在给定的代表垂直线高度的数组 height 中，找出两条线，使其与 x 轴共同构成的容器能容纳的水量最大。

容器的容量由两个因素决定：

宽度 (width)：两条线在 x 轴上的距离，即它们索引的差 j - i。
高度 (height)：两条线中较短的那一条的高度，因为水面不能超过较短的板，即 min(height[i], height[j])。

因此，由索引 i 和 j 的两条线构成的容器的储水量（面积）可以表示为：
Area(i, j) = (j - i) * min(height[i], height[j])

我们的任务就是找到一个 (i, j) 组合，使得这个 Area 值最大。

2. 思路一：暴力解法

最直观的方法是尝试所有可能的线对组合，计算它们的面积，然后找出其中的最大值。

我们可以使用两层循环：

外层循环遍历 i 从 0 到 n-2。
内层循环遍历 j 从 i+1 到 n-1。
在内层循环中，计算 Area(i, j) 并与一个全局最大值 maxArea 比较，如果当前面积更大，则更新 maxArea。

复杂度分析：

时间复杂度：O(n²)。因为需要两层嵌套循环来检查所有 n(n-1)/2 种可能的组合。当 n 达到 10⁵ 时，计算量大约是 10¹⁰ 级别，这在标准的时间限制（通常是 1 秒）内是无法完成的，会导致超时。
空间复杂度：O(1)。我们只需要常数级别的额外空间来存储最大面积和循环变量。

这个方法虽然简单，但效率太低，需要寻找更优的解法。

3. 思路二：双指针法（最优解）

我们可以通过一种更聪明的方式来缩小搜索范围，从而避免暴力枚举。这就是双指针法。

核心思想：
容器的面积由宽度和 短板高度 共同决定。要使面积最大，我们希望宽度和高度都尽可能大。

算法步骤：

初始化：
- 设置两个指针，left 指向数组的起始位置（索引 0），right 指向数组的结束位置（索引 n-1）。
- 初始化一个变量 maxArea 为 0，用来记录最大面积。
- 此时，left 和 right 指针构成了最宽的容器。
循环与移动：
- 当 left 指针在 right 指针左边时（left < right），执行循环。
- 在每次循环中，计算当前指针 left 和 right 所构成容器的面积：
  - width = right - left
  - height = min(height[left], height[right])
  - currentArea = width * height
- 更新最大面积：maxArea = max(maxArea, currentArea)。
- 移动指针：现在我们需要决定是移动 left 指针还是 right 指针，以寻找可能更大的面积。
  - 当前容器的面积受限于较短的那条线（短板）。假设 height[left] < height[right]。
  - 如果我们移动较长的 right 指针（right--），新的宽度 width' 会变小，而新的高度 height' 取决于 min(height[left], height[right_new])。由于 height[left] 已经是短板，新的高度 height' 不可能超过 height[left]。所以，新面积 width' * height' 必然小于当前面积。移动长板没有任何益处。
  - 因此，我们应该尝试移动较短的那条线的指针。如果我们移动 left 指针（left++），宽度 width' 同样会变小，但我们有机会找到一个更高的 height[left_new]，它可能与 height[right] 组成一个更大的面积，从而弥补宽度的损失。
- 决策规则：
  - 如果 height[left] < height[right]，则移动左指针：left++。
  - 否则（height[left] >= height[right]），移动右指针：right--。
结束：
- 当 left 和 right 相遇时（left >= right），循环结束。
- 返回 maxArea。

举例说明 (
[1,8,6,2,5,4,8,3,7]):

left	right	h[left]	h[right]	width	height	Area	maxArea	移动
0	8	1	7	8	1	8	8	left++
1	8	8	7	7	7	49	49	right–
1	7	8	3	6	3	18	49	right–
1	6	8	8	5	8	40	49	right– (或 left++)
1	5	8	4	4	4	16	49	right–
…	…	…	…	…	…	…	…	…

这个过程不断缩小宽度，但通过总是移动短板，保留了找到更高“新短板”的可能性，从而确保不会错过任何潜在的最优解。

复杂度分析：

时间复杂度：O(n)。left 和 right 指针总共只会遍历整个数组一次。
空间复杂度：O(1)。我们只使用了常数个额外变量。

这是一种非常高效的解法，完全满足题目的性能要求。

答案

class Solution {
    /**
     * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * 返回容器可以储存的最大水量。
     *
     * @param height 代表垂直线高度的数组
     * @return 容器可以储存的最大水量
     */
    public int maxArea(int[] height) {
        // 检查输入是否有效，虽然题目保证了 n >= 2，但这是一个好习惯
        if (height == null || height.length < 2) {
            return 0;
        }

        // 初始化双指针
        int left = 0; // 左指针，从数组头部开始
        int right = height.length - 1; // 右指针，从数组尾部开始

        // 用于记录最大面积（储水量）
        int maxArea = 0;

        // 当左指针在右指针左边时，持续循环
        while (left < right) {
            // 计算当前容器的宽度
            int width = right - left;

            // 计算当前容器的高度，由较短的板决定
            int h = Math.min(height[left], height[right]);
          
            // 计算当前容器的面积
            int currentArea = width * h;
          
            // 更新最大面积
            maxArea = Math.max(maxArea, currentArea);

            // 移动指针的决策：
            // 为了寻找可能更大的面积，我们应该移动指向较短板的那个指针。
            // 因为面积受限于短板，移动短板指针，才有可能找到一个更高的板，
            // 从而弥补宽度减小的损失，获得更大的面积。
            if (height[left] < height[right]) {
                left++; // 左边是短板，移动左指针
            } else {
                right--; // 右边是短板（或一样高），移动右指针
            }
        }

        // 循环结束，返回找到的最大面积
        return maxArea;
    }
}