LeetCode 11｜盛最多水的容器：从暴力枚举到双指针优化 | 星雨笔录
本题求数组两线间“短板×宽度”的最大值。暴力法枚举全以 LeetCode 11「盛最多水的容器」为例，从最直观的暴力枚举出发，逐步推导标准双指针与双指针剪枝三种解法。结合短板效应、算法正确性证明、黑盒与白盒测试、详细执行步骤及复杂度分析，深入理解双指针算法的优化原理，并提供 C、C++、Java、Python、JavaScript 五种语言的完整注释实现。部组合（O(n²)），双指针法则通过每次移动较短的指针向中心靠拢，以 O(n) 时间高效求解，是本题最优解。
一、题目描述
题目： LeetCode 11. 盛最多水的容器（中等）
给定一个长度为 n 的非负整数数组 height。数组中第 i 个数表示一块竖直木板的高度，这块木板位于横坐标 i。从中选择两块不同的木板，连同它们之间的 x 轴组成一个容器，求容器最多能够盛多少水。
注意：木板只能竖直放置，容器不能倾斜；没有被选中的中间木板不影响计算。
1.1 输入、输出与计算公式
- 输入： 整数数组
height，其中height[i]是下标i对应的木板高度。 - 输出： 最大盛水量（以单位宽度和单位高度形成的面积表示）。
- 下标约束： 必须选择
0 <= i < j < n的两块木板。
容器的宽度是两块木板的横坐标之差：j - i；水面的高度由较矮的木板决定：min(height[i], height[j])。因此：
我们需要求：
为什么取较短的木板？想象左侧木板高 8，右侧木板高 7：水位一旦超过 7，就会从右侧溢出；即使左侧还有 1 个单位高度，也装不住更多的水。
1.2 题目示例
输入：height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
输出：49
解释：选择下标 1 和下标 8：
左侧高度 = 8，右侧高度 = 7
容器宽度 = 8 - 1 = 7
有效水位 = min(8, 7) = 7
盛水面积 = 7 × 7 = 49
1.3 约束条件
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4
读题时需要注意的数据规模： 若枚举所有两块木板的组合，需要检查 n(n-1)/2 对。n = 10^5 时，组合数达到约 50 亿，因此我们需要寻找比两层循环更高效的方法。
在本题给定约束下，面积最大不超过 (10^5 - 1) × 10^4 = 999,990,000，可以使用 C/C++/Java 的 32 位 int 保存；如果推广到更大的高度或更长的数组，才需要考虑使用更宽的整数类型。
二、测试用例
写算法前，先弄清楚哪些输入必须得到哪些结果。下面先按题意设计黑盒测试，再针对程序内部条件分支设计白盒测试。三种解法都应该通过同一组测试。
2.1 黑盒测试：根据输入输出验证结果
黑盒测试不关心代码怎么写，只检查程序输出是否符合题意。使用等价类划分与边界值分析，覆盖普通输入、最短数组、零高度、重复高度及较大数据规模。
| 编号 | 输入height |
期望输出 | 测试目的 |
|---|---|---|---|
| B01 | [1,8,6,2,5,4,8,3,7] |
49 |
官方经典样例，最优边界不一定在数组两端 |
| B02 | [1,1] |
1 |
最小长度，恰好两块木板 |
| B03 | [0,0] |
0 |
所有高度为零 |
| B04 | [4,3,2,1,4] |
16 |
两端较高，中间较低 |
| B05 | [1,2,1] |
2 |
最优解为两端，宽度较重要 |
| B06 | [2,2,2,2] |
6 |
所有高度相等 |
| B07 | [0,2,0,3] |
4 |
高度中存在零，但答案非零 |
| B08 | [5,0,0,0,5] |
20 |
中间木板不影响选中两端的面积 |
| B09 | [1,2,3,4,5] |
6 |
严格递增，最优解不取第一块 |
| B10 | [5,4,3,2,1] |
6 |
严格递减 |
| B11 | [8,8,8,8] |
24 |
相等高度的指针移动分支 |
| B12 | [10000,0,0,10000] |
30000 |
高度上限及乘法 |
大规模测试： 长度为 100000 的数组，每项均为 10000，期望结果为 999990000。这组数据还可以验证优化算法是否能够在合理时间内完成，而不是采用平方级枚举。
注意：n < 2、负高度或 null 不属于本题规定的合法输入范围，可以在实际工程接口中另行规定行为；不要为了处理题目未要求的情况，使主要算法逻辑变复杂。
2.2 白盒测试：检查条件分支与循环行为
白盒测试关注代码内部是否执行了预期的分支。针对后文的双指针算法，可以重点检查：
| 编号 | 输入 | 关注的执行路径 |
|---|---|---|
| W01 | [1,3] |
左边较矮，移动left |
| W02 | [3,1] |
右边较矮，移动right |
| W03 | [3,3] |
两边相等，执行约定的相等分支 |
| W04 | [0,0] |
当前面积为零，循环仍能正常结束 |
| W05 | [1,8,6,2,5,4,8,3,7] |
多轮移动、不断比较并更新最大面积 |
| W06 | [1,1,1,1,9] |
剪枝法连续跳过无法改进答案的高度 |
这些是覆盖目标和测试数据，不等同于已经用覆盖率工具证明了 100% 分支覆盖。实际执行时可以为 left、right、area、maxArea 加断点，观察每一轮的变化。
另外可以进行随机对拍：随机生成长度为 2～30、高度为 0～20 的数组，用暴力枚举作为参考结果，和两种双指针算法逐次比较。如果任一次结果不同，就说明至少有一种实现存在错误。这能补充固定用例不容易发现的边界组合。
三、解法一：暴力枚举——把所有可能的答案算一遍
3.1 核心思想
既然答案来自两块木板，就先不急着优化：把所有不同的木板组合都检查一遍，算出每一组能够盛多少水，再选出最大的面积。
例如有 4 块木板 [1, 3, 2, 4]，可选的下标组合有 (0,1)、(0,2)、(0,3)、(1,2)、(1,3)、(2,3)，总共 6 组。只要这些组合全部考虑，就一定不会漏掉最大值。
这也是解决最值问题时最容易想到的起点：先保证正确，再分析哪些计算可以省略。
3.2 执行步骤
- 定义
maxArea = 0，记录目前找到的最大盛水面积；还没有检查任何组合时，初始值设为零。 - 从左到右选择第一块木板，下标记为
i。由于右侧至少还要存在一块木板，所以i最多遍历到n - 2。 - 对当前
i，依次选择它右边的第二块木板，下标j从i + 1到n - 1。这样既不会选到同一块木板，也不会重复枚举(j, i)。 - 计算两块木板间的宽度
j - i，再取两块木板高度的较小值，二者相乘得到当前面积area。 - 如果
area大于已经记录的maxArea，就更新maxArea；否则不变。 - 内层循环结束后，换下一个
i，继续寻找新的组合。全部组合处理完毕，返回maxArea。
以 [1,3,2,4] 为例：
木板下标(i,j) |
较矮高度 | 宽度 | 当前面积 | 遍历至此的最大面积 |
|---|---|---|---|---|
(0,1) |
1 | 1 | 1 | 1 |
(0,2) |
1 | 2 | 2 | 2 |
(0,3) |
1 | 3 | 3 | 3 |
(1,2) |
2 | 1 | 2 | 3 |
(1,3) |
3 | 2 | 6 | 6 |
(2,3) |
2 | 1 | 2 | 6 |
最终结果为 6，由下标 1 和 3 的两块木板形成。
3.3 代码实现
下面五种语言采用相同的两层循环逻辑。每份代码均使用 LeetCode 的函数签名，可以单独提交，不需要额外添加 main。
::: code-group C|C++|Java|Python|JavaScript
int maxArea(int* height, int heightSize) {
// maxArea 保存已经检查过的组合中最大的盛水面积
int maxArea = 0;
// i 表示左侧木板；必须给右侧至少留一块木板
for (int i = 0; i < heightSize - 1; i++) {
// j 表示右侧木板，从 i + 1 开始避免重复与自身配对
for (int j = i + 1; j < heightSize; j++) {
// 水位由较矮的木板决定
int minHeight = height[i] < height[j]
? height[i] : height[j];
// 容器面积 = 较矮高度 × 两块木板之间的距离
int area = minHeight * (j - i);
// 如果当前组合更好，就记录这个答案
if (area > maxArea) {
maxArea = area;
}
}
}
// 所有左右木板组合已枚举完毕
return maxArea;
}
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
int maxArea = 0; // 保存目前最大的面积
int n = height.size(); // 木板数量
// 外层循环固定左侧木板 i
for (int i = 0; i < n - 1; ++i) {
// 内层循环尝试 i 右边的所有木板 j
for (int j = i + 1; j < n; ++j) {
// 较矮木板决定水位，距离决定宽度
int minHeight = min(height[i], height[j]);
int width = j - i;
int area = minHeight * width;
// 每检查一个组合，就更新目前最优答案
maxArea = max(maxArea, area);
}
}
return maxArea;
}
};
class Solution {
public int maxArea(int[] height) {
int maxArea = 0; // 当前找到的最大盛水面积
int n = height.length; // 木板总数
// 第一层循环：确定左边界 i
for (int i = 0; i < n - 1; i++) {
// 第二层循环：枚举 i 右侧的每一块木板 j
for (int j = i + 1; j < n; j++) {
// 水位取决于两块木板中较矮的一块
int minHeight = Math.min(height[i], height[j]);
// 相邻下标差就是宽度，而不是木板数量
int width = j - i;
int area = minHeight * width;
// 如果这个容器更大，就覆盖旧答案
maxArea = Math.max(maxArea, area);
}
}
// 两层循环结束，所有合法下标组合都已检查
return maxArea;
}
}
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = 0 # 当前最大的盛水面积
n = len(height) # 木板的数量
# 固定左边界 i，最后一块木板不能单独作为左边界
for i in range(n - 1):
# 从 i 右侧依次枚举所有可能的右边界 j
for j in range(i + 1, n):
# 水位由较矮木板决定，宽度为 j - i
min_height = min(height[i], height[j])
width = j - i
area = min_height * width
# 保存迄今为止检查过的最大面积
max_area = max(max_area, area)
return max_area
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxArea = 0; // 保存已找到的最大面积
const n = height.length; // 木板数量
// 外层循环决定左侧木板的位置
for (let i = 0; i < n - 1; i++) {
// 内层循环枚举其右边所有合法木板
for (let j = i + 1; j < n; j++) {
// 容器高度由短板决定，容器宽度由下标差决定
const minHeight = Math.min(height[i], height[j]);
const width = j - i;
const area = minHeight * width;
// 新面积更大时更新结果
maxArea = Math.max(maxArea, area);
}
}
return maxArea;
};
:::
3.4 复杂度分析
- 时间复杂度：
O(n²)。外层循环执行n - 1次，内层依次执行n - 1、n - 2、...、1次，总枚举次数为n(n - 1) / 2，属于平方级。 - 空间复杂度：
O(1)。除了i、j、area、maxArea等固定数量变量，没有申请随n增长的辅助数组。
暴力法的优点是正确性直观，也适合作为随机对拍的参考实现；问题是当 n 达到 10^5 时，组合数过大，不能满足通常的执行时间要求。
接下来需要回答的问题是：既然许多组合不可能比当前答案更好，能不能直接跳过它们？
四、解法二：双指针——只移动较矮的木板
4.1 核心思想
暴力法最大的浪费，在于它不加区分地尝试每一种宽度和高度组合。实际上，对于某一对左右木板，我们可以利用面积公式排除一批不可能更优的选择。
容器面积为：
先让两块木板处在数组最左端和最右端，此时宽度最大。之后如果要尝试新的组合，指针只能向中间移动，宽度必然缩小。若想获得更大的面积，新的较矮高度就必须足够高，弥补宽度的损失。
关键问题是：左边和右边，应该舍弃哪块木板？
假设左边高度是 3，右边高度是 8，宽度是 6，当前面积就是 3 × 6 = 18。
- 如果把右边的高木板向左移动，左侧高度 3 不变，新宽度小于 6，所以新面积最多只能是
3 × 5 = 15，不可能超过 18。 - 如果把左边的矮木板向右移动，新木板有机会超过 3，虽然宽度缩短了，却有可能用更高的水位取得更大面积。
因此得到规则：每次算完面积，移动高度较小的一侧；两边相等时移动任意一侧即可。
4.2 执行步骤
- 令
left = 0、right = n - 1，指向最左和最右的两块木板；用maxArea = 0记录最大面积。 - 只要
left < right，说明两块木板仍然不同，就继续执行循环。 - 读取两侧高度
height[left]、height[right]；取其中较小的作为水位，同时计算宽度right - left。 - 两者相乘得到当前面积
area，并用它更新maxArea。先计算当前组合，后移动指针，否则就会漏掉本轮容器。 - 比较两侧高度：如果左侧较矮，就执行
left++；否则执行right--。高度相等时这里约定移动右侧，换成移动左侧也正确。 - 重复计算与移动，直到
left >= right。两指针相遇后宽度为零，没有继续计算的意义，返回maxArea。
和两层枚举最大的不同是：这里不会重新把左右指针往外移动，也不会回头检查已经排除的组合。
4.3 手工模拟
以经典示例 [1,8,6,2,5,4,8,3,7] 为例：
| 轮次 | left |
right |
两侧高度 | 当前面积 | maxArea |
下一步 |
|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 1, 7 |
1×8 = 8 |
8 | 左边短，left++ |
| 2 | 1 | 8 | 8, 7 |
7×7 = 49 |
49 | 右边短，right-- |
| 3 | 1 | 7 | 8, 3 |
3×6 = 18 |
49 | right-- |
| 4 | 1 | 6 | 8, 8 |
8×5 = 40 |
49 | 等高，约定right-- |
| 5 | 1 | 5 | 8, 4 |
4×4 = 16 |
49 | right-- |
| 6 | 1 | 4 | 8, 5 |
5×3 = 15 |
49 | right-- |
| 7 | 1 | 3 | 8, 2 |
2×2 = 4 |
49 | right-- |
| 8 | 1 | 2 | 8, 6 |
6×1 = 6 |
49 | right-- |
两指针最终相遇，最大面积仍然是 49。可见当前面积变小是正常现象，不能因此结束搜索；我们真正保存的是所有已检查组合中的最大值。
4.4 为什么移动短板不会漏掉最优解？
这一步是双指针算法的正确性依据，而不是一个只能背诵的口诀。
设当前 height[left] <= height[right]，即左侧是短板。当前容器面积：
如果仍然使用左侧这块木板，而把右侧边界换成任何更靠左的位置 k（left < k < right），就有：
由于 min(height[left],height[k]) <= height[left]，而且 k-left < right-left，所以：
也就是说：对于当前这块左侧短板，向内寻找任何右边界，都不可能比刚刚检查过的当前组合更好。 既然当前面积已经和 maxArea 比较过，就可以安全舍弃这块左侧短板。
当右侧较矮时，论证完全对称。若两侧高度相等，两种舍弃方向都成立。
每一次移动都至少排除一块已证明无需继续参与搜索的边界，最终留下的最大值不会错过全局最优解。
4.5 流程图
4.6 代码实现
五种语言保持同样的处理顺序：初始化指针 → 计算面积 → 更新最大值 → 移动短板 → 返回答案。
::: code-group C|C++|Java|Python|JavaScript
int maxArea(int* height, int heightSize) {
// 两个指针分别指向最左、最右的木板
int left = 0;
int right = heightSize - 1;
int maxArea = 0; // 记录已经找到的最大面积
// 两个指针不能重合：必须由两块不同木板形成容器
while (left < right) {
// 宽度：当前两块木板的下标距离
int width = right - left;
// 水位：只能达到左右两块木板中较矮的一块
int minHeight = height[left] < height[right]
? height[left] : height[right];
// 先计算当前容器的面积，再考虑移动哪一侧
int area = width * minHeight;
if (area > maxArea) {
maxArea = area;
}
// 舍弃短板：保留长板，才有机会提高新的有效水位
if (height[left] < height[right]) {
left++;
} else {
// 右边较矮或两边等高，统一移动右指针
right--;
}
}
return maxArea; // 全部可能改进答案的边界已检查完毕
}
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0; // 最左侧木板
int right = (int)height.size() - 1; // 最右侧木板
int maxArea = 0; // 当前最大面积
while (left < right) {
// 当前容器的宽度 = 两个下标之差
int width = right - left;
// 较矮的一侧限制了容器能够盛水的高度
int minHeight = min(height[left], height[right]);
int area = width * minHeight;
// 不论面积是否增加，都先完成本轮比较
maxArea = max(maxArea, area);
// 每次只移动一个指针，因此不会遗漏已排除的组合
if (height[left] < height[right]) {
++left; // 左边更矮，舍弃左边
} else {
--right; // 右边更矮或等高，舍弃右边
}
}
return maxArea;
}
};
class Solution {
public int maxArea(int[] height) {
// 初始化两端的指针，先考虑宽度最大的组合
int left = 0;
int right = height.length - 1;
int maxArea = 0;
// 指针相遇时无法再形成有宽度的容器
while (left < right) {
// 容器宽度由下标之差决定
int width = right - left;
// 水面的最高位置由较矮木板决定
int minHeight = Math.min(height[left], height[right]);
// 计算本轮面积，保留更大的那个答案
int area = minHeight * width;
maxArea = Math.max(maxArea, area);
// 宽度必然缩小，所以优先尝试提高短板高度
if (height[left] < height[right]) {
left++; // 左侧较矮，移动左指针
} else {
right--; // 右侧较矮或相等，移动右指针
}
}
// 返回整个搜索过程中出现过的最大面积
return maxArea;
}
}
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0 # 初始左边界
right = len(height) - 1 # 初始右边界
max_area = 0 # 已知的最大面积
# 保证左右指针指向两块不同的木板
while left < right:
# 当前宽度与短板高度决定了盛水面积
width = right - left
min_height = min(height[left], height[right])
area = width * min_height
# 无论面积变大还是变小，都与历史最大值比较
max_area = max(max_area, area)
# 只有舍弃较矮的一边，才可能找到更高的短板
if height[left] < height[right]:
left += 1 # 移动左边界
else:
right -= 1 # 移动右边界（包含等高情况）
return max_area
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let left = 0; // 左指针：最左侧木板
let right = height.length - 1; // 右指针：最右侧木板
let maxArea = 0; // 搜索过程中的最大盛水面积
while (left < right) {
// 先得到当前容器的宽度与短板高度
const width = right - left;
const minHeight = Math.min(height[left], height[right]);
// 面积 = 宽度 × 短板高度
const area = width * minHeight;
maxArea = Math.max(maxArea, area);
// 舍弃短板，逐步缩小搜索区间
if (height[left] < height[right]) {
left++; // 左边更矮，左指针右移
} else {
right--; // 右边更矮或等高，右指针左移
}
}
return maxArea;
};
:::
4.7 复杂度分析
- 时间复杂度：
O(n)。每轮至少有一个指针向中间移动一次，right - left从n - 1逐步减少到0，恰好进行n - 1轮，不再枚举平方级组合。 - 空间复杂度：
O(1)。仅使用left、right、width、area、maxArea等有限变量，没有额外数组或哈希表。
相较于暴力法，这次优化真正降低了时间复杂度的数量级：把两层枚举压缩成一次从两端向中间的扫描。这就是本题最值得掌握的标准解法。
五、解法三：双指针剪枝——连续跳过无效高度
5.1 核心思想
标准双指针每一轮只移动一个位置。但我们还可以问：如果移动后遇到的木板不比刚刚舍弃的短板更高，还值得单独计算面积吗？
假设当前左边较矮，且左边高度为 3。计算完面积后，我们决定向右移动左指针。如果接下来连续出现高度 1、2、3，这些木板都不超过已经舍弃的高度 3，但右边界保持不变、宽度继续缩小。
这些位置产生的面积不仅不可能超过刚才算出的面积，而且在后续继续收缩右边界时也不可能构成更好的答案。因此可以直接跳过所有高度小于或等于原短板的木板，直到找到一块更高的木板，或者两个指针已经相遇。
这里的剪枝不是改变最终结果，而是减少部分数据上的无意义面积计算。它与标准双指针一样都是 O(n)，没有进一步降低渐近时间复杂度。
5.2 执行步骤
- 初始化
left = 0、right = n - 1、maxArea = 0。 - 在
left < right时，计算当前宽度和短板高度，得出area，并更新maxArea。 - 如果
height[left] < height[right]，先保存左侧短板的高度oldHeight = height[left]，然后向右移动左指针。 - 移动左指针后，只要
left < right且新的height[left] <= oldHeight，就继续移动左指针；这些高度不超过旧短板、宽度却更小的木板不值得再单独计算。 - 如果右侧高度小于或等于左侧，执行对称操作：保存右侧旧高度
oldHeight = height[right]，向左移动右指针，并连续跳过高度<= oldHeight的木板。 - 当找到有机会提高短板高度的新位置时，重新计算面积；两指针相遇后返回
maxArea。
例如 [1,1,1,1,9]：
- 第一次计算最外侧容器：短板高度 1、宽度 4，面积为 4。
- 左边是短板，保存
oldHeight = 1。 - 向右移动时，新的左侧木板连续为
1、1、1，都不高于原来的短板，可连续跳过。 - 指针最终相遇，返回 4。标准双指针会进行 4 次面积计算，而该剪枝版本只进行 1 次。
5.3 为什么可以连续跳过？
设当前待舍弃的短板高度为 H，当前两边界相距 W，我们已经计算过面积 H × W。对于向内移动后遇到的某块木板，若其高度 h <= H，且未来左右边界只会继续收缩，则它参与形成的任何后续容器都满足：
所以这些组合不可能优于刚刚检查过的面积，可以安全跳过。注意剪枝条件必须是相对于移动前保存的旧短板高度判断，而不是随意和当前另一侧进行比较。
5.4 代码实现
下面使用 oldHeight 表示本轮刚刚处理过的短板高度。内层 while 只是让指针跳过无效位置，不需要回退指针，也不需要额外存储数据。
::: code-group C|C++|Java|Python|JavaScript
int maxArea(int* height, int heightSize) {
int left = 0;
int right = heightSize - 1;
int maxArea = 0;
while (left < right) {
// 先计算当前两块木板形成的容器面积
int minHeight = height[left] < height[right]
? height[left] : height[right];
int area = minHeight * (right - left);
if (area > maxArea) {
maxArea = area;
}
if (height[left] < height[right]) {
// 左侧是短板：记住它的旧高度，作为剪枝阈值
int oldHeight = height[left];
// 高度没有超过 oldHeight 的左侧木板都可以跳过
do {
left++;
} while (left < right && height[left] <= oldHeight);
} else {
// 右侧是短板，或两侧等高：对称地移动右指针
int oldHeight = height[right];
do {
right--;
} while (left < right && height[right] <= oldHeight);
}
}
return maxArea;
}
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = (int)height.size() - 1;
int maxArea = 0;
while (left < right) {
// 当前面积仍然必须先计算，不能跳过边界对
int minHeight = min(height[left], height[right]);
int area = minHeight * (right - left);
maxArea = max(maxArea, area);
if (height[left] < height[right]) {
// 旧左短板决定本次可跳过的高度范围
int oldHeight = height[left];
do {
++left;
} while (left < right && height[left] <= oldHeight);
} else {
// 旧右短板决定本次可跳过的高度范围
int oldHeight = height[right];
do {
--right;
} while (left < right && height[right] <= oldHeight);
}
}
return maxArea;
}
};
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
// 第一步：先计算当前左右木板能形成的面积
int minHeight = Math.min(height[left], height[right]);
int area = minHeight * (right - left);
maxArea = Math.max(maxArea, area);
// 第二步：根据短板所在的一侧进行剪枝
if (height[left] < height[right]) {
// 保存旧左短板，后续遇到不高于它的木板直接跳过
int oldHeight = height[left];
do {
left++;
} while (left < right && height[left] <= oldHeight);
} else {
// 保存旧右短板，连续跳过无法提高水位的位置
int oldHeight = height[right];
do {
right--;
} while (left < right && height[right] <= oldHeight);
}
}
// 剪枝仅省略不可能改进答案的组合，不改变正确结果
return maxArea;
}
}
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
max_area = 0
while left < right:
# 先计算当前两侧木板形成的实际面积
min_height = min(height[left], height[right])
area = min_height * (right - left)
max_area = max(max_area, area)
if height[left] < height[right]:
# 左侧为短板，后续只关心能否找到更高的左木板
old_height = height[left]
left += 1
# 跳过所有不高于旧短板的位置
while left < right and height[left] <= old_height:
left += 1
else:
# 右侧较矮或两侧等高：对称处理右边界
old_height = height[right]
right -= 1
while left < right and height[right] <= old_height:
right -= 1
return max_area
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let left = 0;
let right = height.length - 1;
let maxArea = 0;
while (left < right) {
// 每轮首先计算当前左右边界所能得到的面积
const minHeight = Math.min(height[left], height[right]);
const area = minHeight * (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
// 左边较矮：连续跳过不高于旧短板的木板
const oldHeight = height[left];
do {
left++;
} while (left < right && height[left] <= oldHeight);
} else {
// 右边较矮或相等：连续跳过无效的右侧木板
const oldHeight = height[right];
do {
right--;
} while (left < right && height[right] <= oldHeight);
}
}
return maxArea;
};
:::
5.5 复杂度分析
- 时间复杂度：
O(n)。虽然出现了嵌套的while，但left只会向右走、right只会向左走，整个程序中两个指针移动的总次数最多为n - 1，因此不是O(n²)。 - 空间复杂度：
O(1)。只增加了一个保存旧短板高度的变量oldHeight，不依赖输入规模。
性能上的真实取舍： 剪枝版本在某些高度分布中会减少面积计算次数，例如大量相等或连续较低的木板；但它也加入了额外的条件判断，不保证在所有语言、运行环境和数据分布下都比标准双指针更快。实际面试与生产代码中通常优先采用更简单的标准双指针，只有在测试或性能分析表明确有收益时才采用这一写法。
六、总结：不同情况下选择哪一种解法？
| 比较维度 | 暴力枚举 | 标准双指针 | 双指针剪枝 |
|---|---|---|---|
| 核心思路 | 检查每一对木板 | 从两端向内移动短板 | 移动短板并跳过不高于旧短板的位置 |
| 时间复杂度 | O(n²) |
O(n) |
O(n) |
| 额外空间复杂度 | O(1) |
O(1) |
O(1) |
是否适合n = 10^5 |
否 | 是 | 是 |
| 主要价值 | 容易理解、便于校验其他算法 | 简洁、高效，面试首选 | 进一步认识剪枝与常数开销 |
| 推荐场景 | 小数据、算法推导、随机对拍 | LeetCode 提交、面试、常规开发 | 学习优化思想、针对性性能实验 |
整个优化过程可以概括为：
暴力枚举先保证不遗漏任何组合；接着发现面积被短板限制，于是让双指针从最大宽度开始，每轮有依据地舍弃短板；最后再利用“新高度没有变高且宽度还在变窄”的条件，得到跳过无效高度的剪枝版本。
但要明确：前两种方法之间是从 O(n²) 到 O(n) 的复杂度优化；后两种方法之间只是同一复杂度等级下的计算步骤优化。代码行数更多、检查次数更少，并不自动意味着实际运行时间更短。
本题最值得记住的三个判断
- 什么时候想到暴力枚举？ 题目要求从若干候选组合中求最大值，而暂时还不知道哪些组合可以排除时，先枚举所有合法组合，建立正确的参考解。
- 什么时候想到双指针？ 候选答案由左右边界决定，且有能够证明“移动一侧不会错过最优解”的单调性或排除规律时，可以尝试从两端向内搜索。
- 什么时候考虑剪枝？ 已经能够证明某些候选不可能改进已知结果时，再跳过这些候选；证明正确性比减少几行计算代码更重要。
本题一句话记忆：宽度向内移动必然变小，要争取更大的面积，就必须给短板变高的机会，因此每轮移动较矮的一侧。
进一步练习可以选择 LeetCode 42. 接雨水 与 LeetCode 15. 三数之和。它们也能训练双指针思维，但移动规则和证明方法不同，不能直接照搬本题的“移动短板”。