盛最多水的容器

11. 盛最多水的容器

题目分析

刚开始接触到这个题目的时候可能会想着只要将所有情况遍历一遍，先是 i 为左桶沿的所有情况，然后 i+1 ，i+2... 但是这种做法显然不是最优解。不如我们换一种遍历的想法。

刚才我们是想要将所有值都作为桶的一边遍历一遍。要是我们遍历桶底长度呢。

桶底的长度最大值为数组的长度，也就是将数组两端的值作为桶的两边，这样从最大遍历到最小时间复杂度为 O(n)，每次将桶底长度减一，也就是将数组的两端向中间移动一位。选择移动哪一边呢？ 显然是选择较短的那一边。

这种方法是典型的双指针法。

逐步实现：
首先我们需要两个指针指向数组的两端：

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let r = height.length - 1; // 右指针
  let l = 0; // 左指针
};

然后开始遍历数组，每次遍历都将桶底长度减一，并且判断当前的面积是否大于之前的最大面积：

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let r = height.length - 1; // 右指针
  let l = 0; // 左指针
  let max = 0; // 最大面积

  for (let i = 0; i < height.length; i++) {
    // 遍历数组
    let a = Math.min(height[l], height[r]); //最小桶边
    let s = a * (r - l); // 面积
    height[l] > height[r] ? r-- : l++; // 移动指针
    max = Math.max(max, s); // 更新最大面积
  }
  return max;
};

总结

这一题无论是题目的难度，还是最终代码实现的难度，都不高。但是前提是能够想到双指针法的方法，这是一种常见且高效的解题思路。