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

说明:你不能倾斜容器。

输入:[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
示例 3:

输入:height = [4, 3, 2, 1, 4]
输出:16
示例 4:

输入:height = [1, 2, 1]
输出:2

提示:

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

  • 首尾两个指针,左指针,右指针
  • 左指针右移,右指针左移,都会带来宽度的减小,要想面积有变大的可能
  • 就要高度要变大
  • 又根据木桶原理,高度由较矮的bar高决定
  • 所以我们希望较矮的那个bar,能够变高一些——移动较矮的指针,看看能不能变高

const maxArea = (height) => {
  let max_area = 0
  let left = 0, right = height.length - 1
  while (left < right) {
    const curArea = (right - left) * Math.min(height[left], height[right])
    if (curArea > max_area) {
      max_area = curArea
    }
    if (height[left] < height[right]) {
      left++ // 左边较矮,往右移,或许会变高
    } else {
      right-- // 右边较矮,往左移,或许会变高
    }
  }
  return max_area
}

笨蛋、笨蛋!