🔥个人主页：Milestone-里程碑
❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>
<<Git>><<MySQL>>
🌟心向往之行必能至
题目回顾
LeetCode 第 11 题盛最多水的容器是一道经典的双指针应用题目。
题目大意：
- 给定一个整数数组
height，数组中的每个元素代表一条垂直线的高度 - 我们需要选出两条线，与 x 轴组成一个容器
- 目标是让这个容器能装下最多的水（面积最大）
- 注意：容器不能倾斜
示例：输入：height = [1,8,6,2,5,4,8,3,7]输出：49解释：选高度为 8（索引 1）和 7（索引 8）的两条线，容器宽度为 7，高度为 7，面积为7×7=49。
思路解析
1. 暴力解法（思路简单但低效）
最直观的思路是枚举所有可能的两条线的组合，计算它们的面积，然后取最大值。
- 时间复杂度：
O(n²)，需要双重循环遍历所有组合 - 空间复杂度：
O(1)，只需要常数空间
这种方法在数组长度较大时会超时，无法通过所有测试用例。
2. 双指针解法（最优解）
我们可以用双指针法将时间复杂度优化到O(n)，这也是这道题的标准解法。
核心思路：
- 初始化两个指针，
left指向数组开头，right指向数组结尾。 - 计算当前指针所指两条线组成的容器面积：
面积 = (right - left) × min(height[left], height[right]) - 移动高度较小的那个指针：
- 如果
height[left] < height[right]，说明左边的线是 “短板”，移动left指针向右 - 否则，移动
right指针向左
- 如果
- 重复步骤 2-3，直到两个指针相遇。
为什么这样移动指针是正确的？这是一个贪心的策略。因为容器的面积由宽度和短板的高度决定。
- 如果移动较高的那个指针，宽度会减小，而短板的高度不会增加，所以面积只会更小。
- 只有移动较矮的那个指针，才有可能找到更高的线，从而得到更大的面积。
完整代码实现（C++）
cpp
class Solution { public: int maxArea(vector<int>& height) { int left = 0; int right = height.size() - 1; int max_area = 0; while (left < right) { // 计算当前容器的宽度 int width = right - left; // 计算当前容器的面积 int current_area = width * min(height[left], height[right]); // 更新最大面积 max_area = max(max_area, current_area); // 移动高度较小的指针 if (height[left] < height[right]) { left++; } else { right--; } } return max_area; } };复杂度分析
- 时间复杂度：
O(n)，数组中的每个元素最多被访问一次。 - 空间复杂度：
O(1)，只使用了常数级别的额外空间。
测试验证
我们用题目中的示例输入[1,8,6,2,5,4,8,3,7]来验证代码：
- 初始
left=0，right=8，面积为8 × 1 = 8。 - 因为
height[0] < height[8]，移动left到 1。 - 此时
left=1，right=8，面积为7 × 7 = 49，这是目前的最大值。 - 因为
height[8] < height[1]，移动right到 7。 - 继续这个过程，直到指针相遇，最终得到最大面积
49。
总结
双指针法是解决这类数组区间问题的利器，它通过贪心策略，在一次遍历中就找到最优解，时间效率极高。
