题目描述#

给定一个长度为 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 \leq n \leq 10^5$
$0 \leq height[i] \leq 10^4$

思路分析#

第一印象很容易想到用双指针。
首先考虑蛮力法，两层 for 循环穷举计算容积，取其中的最大值。时间复杂度为 $O(n^2)$ 。题目中 $2 \leq n \leq 10^5$，必然超时。
因此，需要在计算过程中逐步缩小 n 的边界。

定义垂线 $x$，垂线 $y$，$x < y$。由题目可知，计算两根垂线之间可以容纳的水，取决于其中的短垂线$min(height[x], height[y])$，此时的容积：$area(x, y) = min(height[x], height[y]) * (y - x)$

缩小边界就需要向内移动两根垂线，并且都会导致底部宽度 $t = y-x-1$ ，一次只移动两根垂线中的一根时：

• 移动长垂线时，容器两边的 $min(height[x], height[y])$ 一定在不断变小，因此移动后，容积一定小于 $area(x, y)$
• 移动短垂线时，容器两边的 $min(height[x], height[y])$ 可能变大也可能变小，因此移动后，容积可能大于也可能小于 $area(x, y)$

证明：#

设，两垂线围成的容积集合为 $S(x, y)$。假设 $height[x] < height[y]$，向内移动短垂线得到 $S(x+1, y)$，相当于缩短边界，消去 $S(x, y-1)$，$S(x, y-2)$，$S(x, y-3)$，…，$S(x, x+1)$，而所有消去的状态容积一定小于 $S(x, y)$，达到缩小边界的目的。

下面开始实际算法流程：

以示例 1 为例。将 x 和 y 分别置于边界的两端，x < y。

x = 0
y = 8
height = [1,8,6,2,5,4,8,3,7]
          ^               ^
          x               y

当前 height[x] < height[y]，则垂线height[0]所有可能的容积都被筛选完了，其当前最大容积就是area = height[0] * (8 - 0)。将短垂线 x 右移一位。

height = [1,8,6,2,5,4,8,3,7]
            ^             ^
            x             y

此时 x 和 y 的边界被限制在 [1, 8]，继续移动短垂线，直到 x == y，退出算法。

算法流程#

1. 初始化：双指针 x = 0， y = height[height.length - 1];
2. 收缩边界，直到 x == y
   1. 更新容积最大值 maxAr；
   2. 选定两垂线中短板，并将其向内收缩一步；
3. 返回最大值 maxAr

复杂度分析#

只遍历一次数组
时间复杂度：$O(n)$
空间复杂度：$O(1)$

代码实现#

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  if (!height.length || height.length === 1) {
    return 0;
  }

  let x = 0;
  let y = height.length - 1;
  let maxAr = 0;
  while (x < y) {
    maxAr = Math.max(maxAr, Math.min(height[x], height[y]) * (y - x));
    if (height[x] < height[y]) {
      x++;
    } else {
      y--;
    }
  }
  return maxAr;
};