11. 盛最多水的容器
题目描述
输入长度为 n 的整数数组 height。在平面上画 n 条竖线，第 i 条线从 (i, 0) 画到 (i, height[i])。
任选两条竖线，它们和 x 轴一起围成一个容器。容器的水面高度取决于两条线中较矮的一条，宽度等于两条线的横坐标之差，容器不能倾斜。
返回所有选法中容器能装下的最大水量，也就是宽度乘以较矮高度的最大值。
示例 1
输入：height = [1,8,6,2,5,4,8,3,7] 输出：49
解释：选高度为 8（下标 1）和 7（下标 8）的两条线，宽度 7，高度 7，水量为 49。
示例 2
输入：height = [1,1] 输出：1
解释：只有两条线，宽 1、高 1，水量为 1。
数据范围
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4
解题思路：双指针收缩
左右指针夹住区间，面积为短板高度乘宽度。移动较短的一侧才可能获得更高短板；移动长板只会缩短宽度且短板不升高。
为什么正确
每次移动后，被排除的边不可能与当前另一边形成更优容器。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
不能移动较高的一侧；面积受短板限制。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxArea(self, height):
l, r, best = 0, len(height)-1, 0
while l < r:
best = max(best, min(height[l], height[r]) * (r-l))
if height[l] < height[r]:
l += 1
else:
r -= 1
return bestclass Solution {
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;
}
}class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1, best = 0;
while (l < r) {
best = max(best, min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return best;
}
};func maxArea(height []int) int {
l, r, best := 0, len(height)-1, 0
for l < r {
best = max(best, min(height[l], height[r])*(r-l))
if height[l] < height[r] {
l++
} else {
r--
}
}
return best
}var maxArea = function(height) {
let 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;
};function maxArea(height: number[]): number {
let 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(n)。
解法 2：枚举所有线对 时间 O(n²)，空间 O(1)
用两层循环枚举每一对下标 i<j，容量为 min(height[i], height[j]) * (j-i)，取最大值。
直接按定义计算，一定正确，可以用来对拍验证双指针。n 达到 10^5 时会超时。双指针的关键是证明「移动较短一边不会错过最优解」，从而把 O(n²) 对线对剪枝成 O(n) 步。
class Solution:
def maxArea(self, height):
n, best = len(height), 0
for i in range(n):
for j in range(i + 1, n):
best = max(best, min(height[i], height[j]) * (j - i))
return bestclass Solution {
public int maxArea(int[] height) {
int n = height.length, best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
return best;
}
}class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size(), best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
best = max(best, min(height[i], height[j]) * (j - i));
return best;
}
};func maxArea(height []int) int {
n, best := len(height), 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
best = max(best, min(height[i], height[j])*(j-i))
}
}
return best
}var maxArea = function(height) {
const n = height.length;
let best = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
return best;
};function maxArea(height: number[]): number {
const n = height.length;
let best = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
return best;
};