[11] 盛最多水的容器

双指针

details

解题思路

要最大化容器能够盛水的面积，面积公式为： [ \text{Area} = \text{min}(height[i], height[j]) \times (j - i) ]

其中，i 和 j 是数组 height 中两条垂直线的索引。要找到能容纳最多水的两条线，我们可以使用 双指针 技巧：

初始化左右指针：分别指向数组的最左端和最右端，即 i = 0 和 j = height.length - 1。
计算当前面积：使用公式计算当前左右指针对应的面积。
移动指针：移动较短的那条线的指针。因为容器的面积取决于较短的那条线，高度更小的那一边无法形成更大的面积，因此我们尝试移动它来寻找可能更大的容器。
重复上述步骤，直到两个指针相遇为止，过程中记录最大面积。

代码实现（双指针法）

function maxArea(height) {
    let left = 0; // 左指针
    let right = height.length - 1; // 右指针
    let maxArea = 0; // 初始化最大面积

    while (left < right) {
        // 计算当前左右指针构成的容器的面积
        let currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea); // 更新最大面积

        // 移动较短的一边，寻找可能的更大面积
        if (height[left] < height[right]) {
            left++; // 左边较短，移动左指针
        } else {
            right--; // 右边较短，移动右指针
        }
    }

    return maxArea; // 返回最大面积
}

代码解释：

初始化指针：left 指向数组的开头，right 指向数组的末尾。
循环：每次计算由 left 和 right 形成的容器面积，并将其与当前最大面积比较。
移动指针：总是移动较短的一边，因为移动较长的一边不会增加面积。
终止条件：当 left 和 right 指针相遇时，遍历结束，返回最大面积。

时间复杂度分析：

每次迭代我们都在做常数时间的运算并移动指针，因此时间复杂度为 (O(n))，其中 (n) 是数组的长度。
空间复杂度为 (O(1))，因为只使用了常数空间来存储指针和面积。

示例

对于输入 height = [1,8,6,2,5,4,8,3,7]，执行过程如下：

初始时，left = 0，right = 8，对应的容器面积为 min(1, 7) * 8 = 8。
因为左边较短，移动左指针，left = 1。
计算新的面积 min(8, 7) * 7 = 49，更新最大面积。
移动右指针，重复此过程，最终找到最大面积为 49。

这个解法有效地减少了时间复杂度，避免了暴力枚举所有可能的线对。