题目描述

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点  (i, ai) 。在坐标内画 n 条垂直线，垂直线 i  的两个端点分别为  (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与  x  轴共同构成的容器可以容纳最多的水。

说明： 你不能倾斜容器，且  n  的值至少为 2。

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

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

来源：LeetCode

思路

用首尾两个指针，每次把较低的一端向中间移动，并更新最大面积。直到两指针会合，扫描结束。得到的最大面积即是结果。

证明一下为啥这样是正确的。

每一个 left, right 的状态, 最大面积为 S(left, right)。然后较短的板子向中移动，其实是忽略了，短板到 长板前一个的这些组合。那么这些忽略掉的状态的面积可能大于 S(left, right) 吗？

答案是不会。从两点来看，

1. 底边比起(left, right), 是更短的。
2. 新短板只能是短板或者更短的板。

解法

/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = height => {
  let left = 0;
  let right = height.length - 1;
  let area = 0;

  while (right - left >= 1) {
    if (height[left] < height[right]) {
      area = Math.max(area, (right - left) * height[left]);
      left++;
    } else {
      area = Math.max(area, (right - left) * height[right]);
      right--;
    }
  }

  return area;
};