[hot100]盛最多水的容器

盛最多水的容器

题目的大概意思就是输入一个数组 然后把这个数组抽象为一个坐标系，横坐标是数组索引，纵坐标是值

比如输入：4 2 1 8 -> (0,4) (1,2) (2,1) (3,8)这几个离散点 然后题目要求求出开这几个离散点的横坐标与纵坐标围成面积的最大值

这个题目可能比较两极分化，想到思路的可能会觉得比较简单，想不到的就觉得比较抽象

其实算法题嘛 五分钟内想不到思路就可以看题解了或者问ai了 看了思路之后自己写一遍，积累一下这种算法的思维

这题最简单的思路就是双指针了

结合这个图来看

比如这样一个示例 让一个指针指向数组最左边 一个指针指向数组最右边

然后比较高度来让这个范围逐渐逼近 定义一个全局maxArea变量来记录逼近过程中最大的面积

我要求最大嘛 所以我们肯定是想寻求一个高度更大的柱子对不对

所以就是左边如果比右边小 我们就让left++(右移) 否则就让right--(左移)

终止条件就算两个指针重合 这个时候面积就是最小的 其实都已经不存在

如果输入时上面的例子 就算right指向8可以一直不动 指向left的一直往右移动，每移动一次就记录面积，最后只返回最大的面积

这个地方一定要认为height[left]>height[right]去left++，你要想，你想保证水最多 是不是要线最高 ，那比较两边的线的高度 ，那肯定时低的那一边动啊 如果高的东的话 就不一定是最大的面积了

所以移动的原则肯定是：比较两条边，哪边小，哪边就往中间靠

import java.util.Scanner; ​ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); String[] split = s.split(" "); int [] arr=new int[split.length]; for(int i=0;i<split.length;i++){ arr[i]=Integer.parseInt(split[i]); } int i = maxArea(arr); System.out.println(i); } public static int maxArea(int[] height) { //定义两个指针 分别指向数组的两端 int left=0; int right=height.length-1; int maxArea=0; while(left<right){ maxArea = Math.max(maxArea, (right - left) * Math.min(height[left], height[right])); if(height[left]<height[right]){ left++; }else{ right--; } } return maxArea; } }

​