数组与字符串之盛最多水的容器 | 春日游, 杏花吹满头

给你 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

分析

双指针法, 由于盛水最多取决于左右柱子中高度低的柱子的高度, 所以当左边高度小于右边高度时, 面积为左边高度height[left] * (right - left), right - left为左右柱子间的间距

代码

Python3

left = 0
right = len(height) - 1
area = 0

while left < right:
  if height[right] > height[left]:
    area = max(area, height[left] * (right - left))
    left += 1
  else:
    area = max(area, height[right] * (right - left))
    right -= 1
return area

JavaScript

function maxArea(height) {
  let left = 0
  let right = height.length - 1
  let area, max = 0

  while (right - left >= 1) {
    // 如果右指针的值大于左指针的值
    if (height[right] > height[left]) {
      // 面积 = 高度低 * 间距
      area = height[left] * (right - left)
      // 左指针右移
      left++
    } else {
      area = height[right] * (right - left)
      // 右指针左移
      right--
    }
    max = Math.max(area, max)
  }
  return max
}