MUYI · 后端工程师的生产级知识体系

Appearance

盛最多水的容器 ​

一、题目（LeetCode 11 · 中等 · Hot100） ​

给定一个长度为 n 的整数数组 height，第 i 条垂线两端点是 (i, 0) 与 (i, height[i])。选两条线与 x 轴构成容器，求最多能装多少水。

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49      // 取下标 1 和 8：min(8,7) * (8-1) = 49

二、思路演进 ​

2.1 暴力：枚举所有线对 ​

C(n,2) 个组合，每个 O(1) 算面积取最大——O(n²)。n = 10^5 时约 5×10^9 次运算，必然超时。和 两数之和 一样，症结在"对所有对逐一验证"，而其中绝大多数对可以被推理提前排除。

2.2 关键洞察：矮的那端没有资格留下 ​

面积公式只有两个因子：min(h[l], h[r]) × (r - l)。

从最宽的状态（l=0, r=n-1）出发，收缩任何一端宽度都会减 1，唯一的变量是高度：

  • 移动较高那端：新高度仍 ≤ 原来较矮那端（水位由短板决定），高度不增、宽度变小 → 面积必然变小。且它衍生出的后续状态全部更小——这些状态可以整体丢弃；
  • 移动较矮那端：高度有机会变大，面积有可能刷新。

所以每轮收缩矮端。这一步不保证立刻变优，但保证了"被舍弃的矮端参与的所有方案"都不是答案，不丢解。n-1 轮收缩覆盖全部有效候选。这是"对撞双指针的排除法"，同族题见 三数之和 与库内旧文 移除元素。

2.3 走一遍 [1,8,6,2,5,4,8,3,7] ​

(l,r)   两端高度   面积            动作
(0,8)   1,7        1*8  = 8       左矮，左进
(1,8)   8,7        7*7  = 49 ★    右矮，右退
(1,7)   8,3        3*6  = 18      右退
(1,6)   8,8        8*5  = 40      等高，任退一端
……之后宽度继续变小，49 不再被刷新

三、复杂度分析 ​

  • 时间 O(n)：每轮循环 l 与 r 的间距减 1，从 n-1 收到 0，严格 n-1 轮，每轮 O(1)。不是"最多 2n 次"那种均摊，是精确计数。
  • 空间 O(1)：只维护 l、r、best 三个变量。

四、代码 ​

java
package org.example;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_11 {

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 期望 49
        System.out.println(maxArea(new int[]{1, 1}));                      // 期望 1
        System.out.println(maxArea(new int[]{4, 3, 2, 1, 4}));             // 期望 16
    }

    public static int maxArea(int[] height) {
        int left  = 0;
        int right = height.length - 1;
        int best  = 0;
        while (left < right) {
            // 先按当前 (left, right) 算面积，再决定收缩哪端——顺序反了会漏掉最宽状态
            int area = Math.min(height[left], height[right]) * (right - left);
            best = Math.max(best, area);

            // 矮端参与的任何方案都不可能更大，收缩它
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }

}

五、坑点 ​

  • 算面积和收缩的顺序：必须先算再收缩，先收缩会把"最宽状态"直接跳过去。
  • 两端等高时移动哪个都对：等高意味着两端都不可能是最优解的参与者。任退一端（甚至同时退）不丢解。
  • 别写成移动高那端：[1,8,...] 反例里移动 8 那端就永远够不到 49。排除法的前提是"舍弃矮端"，不是"舍弃随便一端"。
  • 高度取 min 不是做减法：容器题目按"线"不按"柱"，两条线之间是空的。
  • int 上限：10^4 × 10^5 ≈ 10^9，尚在 int 内但已贴近 2.1×10^9 的上限，数值范围放大一级就要换 long。

六、变形追问 ​

  • 变体一（接雨水，LeetCode 42）：同样是双指针水题，但按列求和。每列水量由"两侧最大值中的较小者 − 当前高"决定，双指针版需同步维护 leftMax / rightMax。两题同屏出现时要能说清"容器取 min、接雨水取两侧 max"的差异。
  • 变体二（改面积定义）：若面积定义改成 (h[l]+h[r]) × (r-l)，"排除矮端"的论证立即失效。原因是移动高端也可能变大。需要重新找单调性——面试现场推导这类"性质变化"正是考察点。

2026-10 新增（E 轨 · Hot100 第一批）。