题目：给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
图如下：摘抄自leetcode
输入：[1,8,6,2,5,4,8,3,7]，输出：49
解法1：.既然给了我们一个数组，而且是求最大的盛水容量，这就避不开遍历循环，利用穷举法进行逐个循环。我们采用i，j下标进行循环遍历，求出最小高度和他们之间的宽度，长*宽就可以求出及具体的体积。这种方法也称为暴力解法。下面给出具体的代码。
package com.cxy.array;
public class MaxArea {
public static int maxArea() {
int[] height = new int[]{1,8,6,2,5,4,8,3,7};
int res = 0;
for(int i=0; i<height.length; i++){
int first = height[i];
for(int j=i+1; j<height.length; j++){
//求出对应的距离
int width = j-i;
//下一个元素的高度
int next = height[j];
//求出最小高度
int minHeight = Math.min(first,next);
//每次循环将最大的值覆盖掉前面的值
res = Math.max(minHeight*width,res);
}
}
//返回值
return res;
}
//测试代码
public static void main(String[] args) {
int i = MaxArea.maxArea();
System.out.println(i);
}
}分析时间复杂度:O(n2) 空间复杂度O(n)，如果数据量更多的话，我们消耗的资源将会更多。
解法2：采用双指针进行动态的求解，其实是穷举法的演变，只是一个指针i,一个指针j，分别指向数组开始和结尾。在这个问题中，影响盛水多少一个是高度，一个是宽度，求最大值，那就宽度 和 两边指针对应的最小值要最大。如果左边指针固定，right[j]>left[i]，如果我们移动右指针的话，下一次的体积一定会比当前小（因为我们已经假设right[j]>left[i]），因为在左指针不动的情况下，右边移动，导致宽度变小，下一次一定比当前小。所以思路就出来了
思路：
if(right[j]>left[i]){移动左指针(i++)}else{移动右指针(j–)}
代码如下
package com.cxy.array;
/**
* 双指针法实现装最多水的体积
* 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为
* (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
* 说明：你不能倾斜容器，且 n 的值至少为 2。
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/container-with-most-water
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class MaxArea2 {
public static int maxArea() {
int[] height = new int[]{1,8,6,2,5,4,8,3,7};
//指向最右边的指针 和 结果
int j = height.length-1,res = 0;
for(int i=0;i<height.length;){
if(i == j){
break;
}
//求出两边睡得长度更小，谁小谁就移动指针
int minH = Math.min(height[i],height[j]);
//将结果与上一次循环出来的结果进行比较，选出最大的一个
res = Math.max(res,minH*(j-i));
System.out.println("计算结果为："+res+" 当给的j值："+j+"当前的最小高度为："+minH+" 中间的长度为"+(j-i));
if(height[i]<height[j]){
i++;
}else {
j--;
}
}
return res;
}
public static void main(String[] args) {
int i = MaxArea2.maxArea();
System.out.println(i);
}
}打印的结果(可以结合代码和分析进行查看)
"C:\Program Files\Java\jdk1.8.0_162\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2019.1.4\lib\idea_rt.jar=54251:C:\Program Files\JetBrains\IntelliJ IDEA 2019.1.4\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_162\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_162\jre\lib\rt.jar;D:\IdeaWorkSpace\Algorithms\JinDianSuanFa\out\production\JinDianSuanFa;D:\mvnrep\junit\junit\4.12\junit-4.12.jar;D:\mvnrep\org\hamcrest\hamcrest-core\1.3\hamcrest-core-1.3.jar;D:\mvnrep\org\jetbrains\annotations\17.0.0\annotations-17.0.0.jar" com.cxy.array.MaxArea2
计算结果为：8 当给的j值：8当前的最小高度为：1 中间的长度为8
计算结果为：49 当给的j值：8当前的最小高度为：7 中间的长度为7
计算结果为：49 当给的j值：7当前的最小高度为：3 中间的长度为6
计算结果为：49 当给的j值：6当前的最小高度为：8 中间的长度为5
计算结果为：49 当给的j值：5当前的最小高度为：4 中间的长度为4
计算结果为：49 当给的j值：4当前的最小高度为：5 中间的长度为3
计算结果为：49 当给的j值：3当前的最小高度为：2 中间的长度为2
计算结果为：49 当给的j值：2当前的最小高度为：6 中间的长度为1
49
Process finished with exit code 0来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com
