LeetCode 11. 盛最多水的容器

约 4 分钟
文章信息 21 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 百度 滴滴 华为 拼多多 小米 商汤 LeetCode 75 LeetCode 热题 100 面试经典 150 题
标签
数组 双指针 贪心 双指针经典题
目录

题目描述

✅ 11. 盛最多水的容器

image-20220919215725853

image-20220919215625287

题意分析

输入是高度数组 height，第 i 条垂线的两端是 (i, 0) 和 (i, height[i])。任选两条线 i < j，与 x 轴围成的容器容积等于 min(height[i], height[j]) * (j - i)：高取两者中的较小值——水面不能高于矮的一侧，否则溢出；宽是两下标之差。

题目明确垂线不可倾斜，容器也不能歪着装，所以容积只由「短板高度」和「宽度」两个量决定，两线之间的其余线既不挡水也不占体积。

约束信号：n 最大可到 $10^5$，两两组合约有 $5 \times 10^9$ 对，暴力枚举必然超时；高度可以为 0，这样的线与任何线组合容积都是 0。

解法：双指针移动短板

核心思路

问题关键：面积为 (right - left) × min(height[left], height[right])。暴力枚举所有线对是 $O(n^2)$，而数据规模要求我们一次排除一批不可能更优的组合。

为什么选双指针：从最宽的两端开始，之后宽度只会变小。若左边更矮，固定左边并把右边向内移动，宽度变小，短板高度又不可能超过 height[left]，面积一定不会更大。因此当前面积已经是左边这条线能得到的最大面积，可以安全丢弃左边；右边更矮时同理。

不变量：每轮开始时，尚未被排除的最优解端点仍在 [left, right] 内。计算当前面积后移动短板，只会删除一个已证明不可能产生更优答案的端点，所以最终不会漏掉最优解。两边等高时移动任意一边都成立。

解题步骤

  1. 令 left = 0、right = n - 1，从最大宽度开始。
  2. 在 left < right 时，计算当前面积并更新最大值；必须先计算，再移动指针。
  3. 比较两端高度，移动较矮的一端；相等时任选一端移动。
  4. 指针相遇后返回最大面积。

以 [1,8,6,2,5,4,8,3,7] 为例，首轮面积为 8，左侧高度 1 是短板，因此移动左指针；下一轮得到面积 7 × 7 = 49。后续虽然继续收缩区间，但不会漏掉更优组合，最终答案为 49。

代码实现

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int ans = 0;

        while (left < right) {
            int minHeight = Math.min(height[left], height[right]);
            ans = Math.max(ans, (right - left) * minHeight);

            // 宽度变小后，只有移动短板才可能找到更大面积。
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
}

func maxArea(height []int) int {
    left := 0
    right := len(height) - 1
    ans := 0

    for left < right {
        h := height[left]
        if height[right] < h {
            h = height[right]
        }
        area := (right - left) * h
        if area > ans {
            ans = area
        }

        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。每轮至少有一个指针向内移动，总共至多移动 n - 1 次。
  • 空间复杂度：$O(1)$。

关键点总结

  • 面积由宽度和短板共同决定；宽度收缩后，只有替换短板才可能变大。
  • 正确性证明的核心不是“经验上移动矮边”，而是“固定矮边后，所有更窄组合都不会更优”。
  • 面试时先写面积公式，再用排除法说明指针移动，逻辑会比直接背模板更完整。

易错点总结

  • 移动较高的一侧没有依据。反例 [1,2,4,3]：一直移动高边只能得到 3，会漏掉下标 1 和 3 组成的面积 4。
  • 宽度是 right - left，不是元素个数 right - left + 1；[1,1] 的正确面积是 1。
  • 必须先计算当前面积再移动短板，否则 [4,3] 的唯一组合会被漏掉。
  • 当前面积并不单调，不能因一次下降就提前结束；样例面积会从 49 降到 18，再回升到 40。

相似题目

题目 难度 考察点
42. 接雨水 困难 逐格储水而非选两条线，需要每格左右最大值或单调栈
167. 两数之和 II - 输入有序数组 中等 对撞指针靠「和的单调性」决定移动方向，而非短板
15. 三数之和 中等 排序后固定一元、内层对撞，重点在去重与剪枝
407. 接雨水 II 困难 二维短板效应，用优先队列从边界最矮处向内推进