手帐 Blog

主题

复盘 · LC 11 盛最多水的容器 ​

题目 ​

题意 ​

竖线高度数组 height，选两条线 i < j，与 x 轴围成容器，面积为 min(height[i], height[j]) * (j - i)，求最大面积。

  • 线本身无厚度；水不会斜着漏。
  • n 可达 10⁵ 量级时，O(n²) 通常过不了。

边界：只有两根线；递增/递减；中间有很高但间距小的柱。

涉及算法 ​

标签一句话
对撞双指针两端起步；每次移动较矮的那一侧
贪心证明直觉宽已最大，矮边决定高；移矮边才可能换到更高

教程对照：05 · 对撞双指针（本篇另一道精讲）。

评价我的解法 ​

先暴力枚举所有对，超时；再按「左右夹逼、移矮边」写出 O(n) 解并通过。

第一版（暴力超时） ​

我的代码（摘自 11-盛最多水的容器/index.js，不含测例）：

javascript
var maxArea = function (height) {
  let max = 0;
  for (let i = 0; i < height.length - 1; i++) {
    for (let j = 1; j < height.length; j++) {
      const n1 = height[i];
      const n2 = height[j];
      const count = Math.min(n1, n2) * (j - i);
      max = Math.max(count, max);
    }
  }
  return max;
};

问题：

  1. O(n²)，注释写明 57/65 TLE——和题规模对不上。
  2. 内层 j 从 1 起、不保证 j > i，当 j ≤ i 时面积非正，不影响 max，但属于多余计算，面试也会被追问。

正确性方向没问题：面积公式写对了。

第二版（对撞） ​

我的代码（摘自 11-盛最多水的容器/index2.js，不含测例）：

javascript
var maxArea = function (height) {
  let max = 0;
  for (
    let i = 0, j = height.length - 1;
    i < height.length - 1 && j > 0 && i <= j;
  ) {
    const n1 = height[i];
    const n2 = height[j];
    const count = Math.min(n1, n2) * (j - i);
    max = Math.max(count, max);
    if (n2 >= n1) {
      i++;
    } else {
      j--;
    }
  }
  return max;
};

对在哪：

  1. 两端起步 + 更新 max + 移较矮侧：核心策略正确，能 AC。
  2. 注释诚实写了「AI 提示思路后写出」——思路借用可以，关键是能否复述「为什么移矮边」。

糙在哪：

  1. 循环条件啰嗦：i < j（或 while (i < j)）足够；一堆边界条件增加心智负担。
  2. 等高时 n2 >= n1 选移左：正确（移任一侧即可）；口述可说「相等时随便移一边，或两边都试一次更细，但非必须」。
  3. 变量名 count 实际是面积，面试口头说 area 更清晰。

小结：暴力会写、优化依赖提示——说明 05 篇「移矮边」的证明还没默写进肌肉。合上笔记再默写一遍 while (l < r) 模板。

最佳题解 ​

同策略，写法更干净：

javascript
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let ans = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]);
    ans = Math.max(ans, h * (right - left));
    if (height[left] <= height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return ans;
};
  • 时间 O(n)，空间 O(1)。
  • 为何更优：宽度从最大往里收；固定矮边时再缩宽只可能更差，故必须换掉矮边。

关联题目 ​

题为何相关
42. 接雨水也是左右高度约束，难点更高
15. 三数之和同一天练的对撞骨架
167. 两数之和 II有序对撞，和大/小移动

一句话带走 ​

盛水容器 = 左右对撞，每次丢掉较矮的那根柱；别枚举所有 (i, j)。