0011.盛最多水的容器

难度：🟡 中等

标签：贪心、数组、双指针

链接：11. 盛最多水的容器

题目描述

给定一个长度为 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

解题思路

核心思想

本题的目标是找到两条垂线，使其形成的容器面积最大。容器的面积由两条线中较短的那条（木桶效应）和它们之间的距离共同决定，即 Area = min(height[i], height[j]) * (j - i)。我们的目标就是最大化这个面积。

思路选择

双指针法 是解决此问题的最优思路。

我们初始化两个指针，left 指向数组的开头，right 指向数组的末尾。此时，两条线之间的距离（宽度）是最大的。
在每一步，我们计算由 left 和 right 指针所构成的容器的面积，并更新最大面积记录。
接下来，我们需要决定移动哪个指针来寻找可能更大的面积。由于容器的高度取决于较短的线，如果我们移动较高的那条线，宽度会减小，而高度最多不变（甚至可能变小），所以面积不可能增大。因此，唯一可能找到更大面积的方法是移动较短的那条线的指针，去“赌”下一个位置的线会更高。

关键步骤

初始化：
- left 指针指向 0。
- right 指针指向 height.length - 1。
- maxArea = 0 用于记录最大面积。
循环条件：当 left < right 时，表示两个指针还未相遇，持续循环。
计算与更新： a. 计算当前容器的面积 currentArea = Math.min(height[left], height[right]) * (right - left)。 b. 更新最大面积 maxArea = Math.max(maxArea, currentArea)。
移动指针： a. 比较 height[left] 和 height[right] 的高度。 b. 如果 height[left] < height[right]，则 left++。 c. 否则，right--。
返回结果：循环结束后，maxArea 中存储的就是能容纳的最大水量。

代码实现

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let left = 0,
    right = height.length - 1;
  let maxArea = 0;
  while (left < right) {
    // 1. 正确计算当前面积并更新最大值
    maxArea = Math.max(
      maxArea,
      Math.min(height[left], height[right]) * (right - left)
    );
    // 2. 正确地移动指向较短板的指针
    if (height[left] < height[right]) left++;
    else right--;
  }

  return maxArea;
};

优点：此实现堪称模板，正确地利用了双指针从两端向中间收缩，并通过贪心策略移动指针，在 O(n) 时间内解决了问题。
代码风格优化: 代码非常清晰、简洁，变量命名也很标准，无需改动。

复杂度分析

时间复杂度：O(n) 其中 n 是数组 height 的长度。left 和 right 指针总共只会遍历整个数组一次。
空间复杂度：O(1) 我们只使用了常数个额外变量作为指针和记录，空间消耗是恒定的。

总结

本题是双指针思想的经典应用。其精髓在于理解：当从最大宽度开始时，唯一可能获得更大面积的途径就是增加容器的高度，而这只能通过移动指向较短板的指针来实现。这种贪心策略确保了我们不会错过任何可能的最优解，同时又极大地提高了算法的效率。

0011.盛水最多的容器