11. 盛最多水的容器（Container With Most Water）

频次 ★★★★ · 难度 🟡 · 高频：腾讯/字节

题目

n 条垂线，第 i 条高 height[i]。选两条线与 x 轴构成容器，求能盛的最多水（面积 = 两线间距 × 较矮线高）。

示例：

输入: [1,8,6,2,5,4,8,3,7]
输出: 49    （下标 1 和 8:宽 7 × 高 min(8,7)=7）

思路

首尾双指针从最宽开始收缩。每步面积 = min(h[l], h[r]) × (r - l)，然后移动较矮的一侧：

• 向内收缩宽度必然减小，面积想变大只能靠高度
• 高度受矮板限制——保留矮板、移动高板，min 不可能变大，面积必然更小
• 所以”以当前矮板为边的所有组合”可以一次性排除，移矮板是安全的剪枝

代码

public int maxArea(int[] height) {
    int l = 0, r = height.length - 1, best = 0;
    while (l < r) {
        best = Math.max(best, Math.min(height[l], height[r]) * (r - l));
        if (height[l] < height[r]) l++;   // 移动矮的一侧
        else r--;
    }
    return best;
}

复杂度

• 时间：O(n) —— 每步排除一个端点
• 空间：O(1)

边界条件

• 只有两条线：直接返回它们的面积
• 两侧等高：移哪边都行（代码走 else 移右侧），不影响最优解
• 含高度 0 的线：面积为 0，正常参与比较

变式

• 输出最优的两个下标：更新 best 时记录 l、r
• 三维版（选两个柱子围水）没有意义——真正的进阶是42. 接雨水：所有柱子共同接水

易错点

• 移动高的一侧——方向反了结果就错，必须能说出”高板受矮板限制”的排除证明
• 面积公式的高是 min，不是两高之和/平均
• 等高时同时移动 l 和 r 会漏解（中间可能有更优组合的边等于当前高度）

面试追问

• 为什么移矮板不会错过最优解？ 标准答案是排除法：固定矮板 l，任何 (l, k) (l<k<r) 宽更小、高 ≤ h[l]，面积都小于当前 (l, r)，所以 l 可以退休。这题考的就是这段证明
• 暴力 O(n²) 和双指针的分界在哪？ 双指针的前提是”每一步能安全排除一个候选端点”，能讲出单调性/排除条件才允许降维

关联题

• 同套路：167. 两数之和II-输入有序、15. 三数之和 —— 首尾双指针靠单调性排除
• 易混：42. 接雨水 —— 本题选两板成容器，那题是所有柱子共同接水，公式与维护量都不同
• 知识点：双指针的本质是每步用 O(1) 判断排除一批候选，专题见双指针