盛最多水的容器

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

Show Time

老样子先开始我们的一顿分析

• 其实就是求最大面积
• 找出宽*高最大值就行

分析完毕

Coding

// 双指针
// 但是效果不是很理想
// 执行用时：952 ms, 在所有 JavaScript 提交中击败了9.14%的用户
// 内存消耗：39.1 MB, 在所有 JavaScript 提交中击败了5.88%的用户
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let length = height.length,
    res = 0

  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      res = Math.max(res, (j - i) * Math.min(height[i], height[j]))
    }
  }
  return res
}

看了官方题解之后,瞬间感觉自己做的真 low 盛最多水的容器

// 真·双指针
// 执行用时：104 ms, 在所有 JavaScript 提交中击败了32.34%的用户
// 内存消耗：38.5 MB, 在所有 JavaScript 提交中击败了5.88%的用户
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let length = height.length,
    index = 0,
    lastIndex = length - 1,
    res = 0

  while (index != lastIndex) {
    let diffIndex = lastIndex - index,
      indexValue = height[index],
      lastIndexValue = height[lastIndex]
    res = Math.max(res, Math.min(indexValue, lastIndexValue) * diffIndex)
    if (indexValue > lastIndexValue) lastIndex--
    else index++
  }

  return res
}