如何解决Leetcode「盛最多水的容器」题目的超时问题？

问题描述 #

我在Leetcode完成了11. Container With Most Water（11. 盛最多水的容器）题目，测试用例通过55/60，状态为time limit exceeded（超时），无具体错误。请问如何修改我的代码以拿到剩余5分？

原代码如下：

/**
 * @param {number[]} height
 * @return {number}
 */

//to get the area between two endpoints
const getArea = (left, right, distance) => {

  if (left <= right) {
    return left * distance;
  } else {
    return right * distance;
  }
}

//this function receive height array to check all areas and find max area
const maxArea = (height) => {

  let left = 0;
  let right = height.length - 1;
  let distance = right - left;
  let maxArea = 0;
  let area = 0;

  // for the conditional of the loop, i use the Gauss sum 
  // to get all possible areas.
  // Example: in the array [2,4,5,10], the possible areas are:
  // [2,4], [2,5], [2,10], [4,5], [4,10], [5,10]
  // using the Gauss sum: n(n+1)/2, where n = array.length-1, 
  // i can get the possible areas, in this case, the result is 6

  for (let i = 0; i < ((height.length - 1) * ((height.length - 1) + 1) / 2); ++i) {

    area = getArea(height[left], height[right], distance);

    if (area > maxArea) {
      maxArea = area;
    }

    //Increase and reduce the pointers to pass to the next possible area
    if (right == left + 1) {
      left++;
      right = height.length - 1;
      distance = right - left;
    } else {
      right -= 1;
      distance--;
    }
  }

  return maxArea;

};

let height = [1, 8, 6, 2, 5, 4, 8, 3, 7];

console.log(maxArea(height));

问题分析 #

你的代码本质是暴力枚举所有可能的容器组合，时间复杂度为O(n²)。当输入数组长度极大时（比如n=10^5），需要计算的组合数会达到数亿级，必然触发超时。

优化方案：双指针法 #

这道题的最优解法是双指针法，时间复杂度可降至O(n)，仅需一次遍历即可找到最大面积。核心逻辑：

• 用两个指针分别指向数组最左端（left=0）和最右端（right=height.length-1）
• 计算当前指针对应容器的面积，更新最大面积
• 移动高度较小的指针：容器高度由较矮的一侧决定，移动较高指针只会减少宽度而无法提升高度，只有移动较矮指针才有可能找到更高的容器，弥补宽度减少的损失
• 重复上述步骤，直到两指针相遇

修改后的代码 #

/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = (height) => {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;
    
    while (left < right) {
        const currentWidth = right - left;
        const currentHeight = Math.min(height[left], height[right]);
        const currentArea = currentWidth * currentHeight;
        
        if (currentArea > maxArea) {
            maxArea = currentArea;
        }
        
        // 移动较矮的一侧指针
        height[left] < height[right] ? left++ : right--;
    }
    
    return maxArea;
};

// 测试用例
let height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log(maxArea(height)); // 输出49

代码说明 #

1. 初始化左右指针和最大面积变量
2. 循环条件left < right保证指针未相遇，仍有组合可计算
3. 计算当前容器的宽度（指针间距）、高度（两侧最小值）和面积
4. 对比当前面积与最大面积，更新最大值
5. 移动较矮的指针：左矮则左移，右矮则右移，保留较高侧以寻找更大面积
6. 循环结束后返回最大面积

这种方法仅遍历数组一次，能高效处理大规模输入，彻底解决超时问题。

内容的提问来源于stack exchange，提问作者M Angel ambrose