LeetCode - 中等 - 盛水最多的容器
image.png

思路：双指针+贪心算法

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5. var maxArea = function (height) {
  6.   if (height.length === 2) {
  7.     return Math.min(height[0], height[1]);
  8.   }
  10.   // 公式：maxArea = Math.min(height[i], height[j]) * Math.abs(i - j)
  11.   let i = 0;
  12.   let j = height.length - 1;
  13.   let ans = 0;
  14.   while (i < j) {
  15.     ans = Math.max(ans, Math.min(height[i], height[j]) * (j - i));
  16.     if (height[i] < height[j]) {
  17.       i++;
  18.     } else {
  19.       j--;
  20.     }
  21.   }
  22.   return ans
  23. };
  25. const res = maxArea([4, 3, 2, 1, 4]);
  26. console.log(res);
  1. 我们选取两个位置i,j，其中i=0，j=height-1,即分别在列表height的首尾
  2. 排除特殊情况height.length===2，此时无需计算，直接根据短板理论返回最小值即可

  3. 我们令双指针分别向数组重心移动，在这里我们需要弄明白一个公式：

    1. maxArea = Math.min(height[i], height[j]) * Math.abs(i - j)
    2. //最大面积 = 较短的边长 x 最大的下标差

  4. 每次移动指针前都需要比对height[i],height[j]的值的大小，确保我们留下较大的那一个，而在小的那一边继续向中心移动，比如：height[i] < height[j]，则j不动而i向右移动

  5. 在这个过程中我们只需要留下最大的Math.min(height[i], height[j]) * (j - i)即可。