最大容量容器问题解析

"盛最多水的容器.md" 这个问题是一个经典的计算机科学算法问题，通常出现在面试或编程竞赛中，属于算法题解的范畴。题目要求找到一组垂直线，这些线由给定非负整数数组的高度定义，使得它们与x轴形成的矩形区域能容纳最多的水。不允许倾斜容器，所以寻找最大面积的关键在于选择合适的两根线。 问题的核心是使用双指针技术来解决。这里有两个指针，一个初始化为数组的起始位置（最小高度），另一个指向数组的末尾（最大高度）。计算当前选定两线段形成的矩形面积，并将其与当前最大面积进行比较，更新最大面积。然后，如果较小高度的线段左侧还有更高的线段，就向右移动较小高度的指针；反之，如果较大高度的线段右侧还有更高的线段，就向左移动较大高度的指针。这样可以保证每次移动都会增加可能的最大面积或者至少保持不变。 给出的参考答案使用C++编写，代码如下： ```cpp #include <bits/stdc++.h> using namespace std; class Solution { public: int maxArea(vector<int>& height) { int min = 0, max = height.size() - 1; int area_max = 0; while (min < max) { int area = (max - min) * (height[min] < height[max] ? height[min] : height[max]); area_max = area > area_max ? area : area_max; if (height[min] < height[max]) { min++; } else { max--; } } return area_max; } }; ``` 在这个解决方案中，`maxArea`函数接收一个`vector<int>`类型的参数`height`，表示各个线段的高度。`min`和`max`分别初始化为数组的第一个元素和最后一个元素的索引。`area_max`用来存储当前找到的最大面积。 循环会一直执行，直到`min`和`max`相遇。在每次循环中，首先计算当前的面积，然后更新`area_max`。之后，根据`min`和`max`所指的高度哪个更小，决定移动哪个指针。这样保证了每次移动都尽可能增加面积或保持面积不变，从而在遍历完整个数组后得到最大面积。 题目给出了四个示例测试用例，分别对应不同的高度数组，以验证算法的正确性。例如，当输入为`[1,8,6,2,5,4,8,3,7]`时，最大面积为49；当输入为`[1,1]`时，最大面积为1。 这个算法的时间复杂度为O(n)，空间复杂度为O(1)，因为它只需要常量级别的额外空间，且只遍历一次数组。因此，这种双指针方法对于处理大规模数据是非常高效的。