算法探秘：盛最多水的容器问题
目录
一、问题引入
二、示例剖析
三、暴力解法与困境
四、双指针法：优雅的解决方案
五、总结
一、问题引入
在算法的奇妙世界里，常常会遇到各种有趣又富有挑战性的问题，“盛最多水的容器”就是其中之一。想象一下，有一系列垂直排列的线段，它们与 x 轴共同构成了一个个容器，我们的任务是找出其中能够容纳最多水的那个容器。具体来说，给定一个长度为 n 的整数数组 height ，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) ，我们要找出其中两条线，使它们与 x 轴构成的容器能容纳最多的水，而且容器不能倾斜哦。
二、示例剖析
先来看两个具体的例子，这样能让我们对问题有更直观的感受。
示例1
输入数组为 [1,8,6,2,5,4,8,3,7] ，在这种情况下，容器能够容纳水的最大值为 49 。从对应的示意图中可以看到，不同竖线构成的容器，其容量是不一样的，我们要找的就是其中最大的那个容量。
示例2
输入数组为 [1,1] ，此时输出的最大容量为 1 。通过这两个简单的例子，相信你已经对问题有了初步的理解。
三、暴力解法与困境
int cmp(const void*e1,const void*e2)
{
return *(int*)e1-*(int*)e2;
}
int maxarea(int* height, int heightSize)
{
int sum=heightSize-1+(heightSize-1)*(heightSize-2)/2;
int*arr=(int*)malloc(sizeof(int)*sum);
int input=0;
for(int i=0;i<heightSize-1;i++)
{
for(int j=heightSize-1;j>i;j--)
{
int temp=height[i]<height[j]?height[i]:height[j];
int mul=temp*(j-i);
arr[input]=mul;
input++;
}
}
qsort(arr,sum,sizeof(int),cmp);
return arr[sum-1];
}
刚开始接触这个问题时，很容易想到暴力枚举的方法。通过两层循环，遍历所有可能的两条线段组合，计算它们构成的容器的容量，然后找出最大值。图中右侧的代码就是一种暴力枚举的实现方式。它先计算出所有可能组合的数量 sum ，然后使用两层循环遍历数组，计算每对线段构成的容器容量并存储在数组 arr 中，最后对数组排序并返回最大值。
但是，这种方法存在一个很大的问题，那就是时间复杂度较高，为 O(n^2) 。当数组规模较大时，程序运行的时间会变得非常长，甚至可能出现超时的情况，这显然不是我们想要的结果。
四、双指针法：优雅的解决方案
为了降低时间复杂度，我们可以采用双指针法。这种方法就像是一场有趣的“指针舞蹈”，让两个指针从数组的两端向中间移动，逐步找到最大容量的容器。
具体代码如下：
c
#include <stdio.h>
int maxArea(int* height, int heightSize) {
int left = 0;
int right = heightSize - 1;
int max_area = 0;
while (left < right) {
int area = (right - left) * ((height[left] < height[right]) ? height[left] : height[right]);
if (area > max_area) {
max_area = area;
}
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max_area;
}
代码开始时，定义两个指针 left 和 right 分别指向数组的起始和末尾位置，同时初始化最大容量 max_area 为 0 。在循环中，每次计算当前指针所指线段构成的容器容量 area ，如果这个容量大于当前记录的最大容量 max_area ，就更新 max_area 。然后，根据两条线段的高度情况，将较矮的那条线段对应的指针向中间移动，直到两个指针相遇，此时返回记录的最大容量 max_area 。
双指针法的时间复杂度为 O(n) ，相比暴力枚举法，效率有了显著提升。因为两个指针从两端向中间移动，最多遍历一次数组，大大减少了计算量。
五、总结
“盛最多水的容器”问题看似简单，却蕴含着丰富的算法思想。从暴力枚举的直观思路到双指针法的巧妙优化，我们不仅学会了解决这个具体的问题，更重要的是掌握了不同算法的特点和应用场景。在未来面对其他算法问题时，也可以借鉴这种从简单到优化的思考方式，不断探索更高效的解决方案，在算法的海洋中畅游，发现更多的乐趣和奥秘。