import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param height int整型一维数组 * @return int整型 */ public int maxArea (int[] height) { // write code here int left=0; int right=height.length-1;//定义左右指针 int max=0;//记录题解的最大值 while(left<right){//循环结束的条件 int v=Math.min(height[left],height[right])*(right-left);//得到边界体积 max=Math.max(v,max);//看是否需要更新最大体积 if(height[left]>height[right]){//判断指针的走向 right--; }else{ left++; } } return max;//最后返回记录的最大值即可 } }
---->我们首先看一个例子,:以【6,2,5,4】举例
一开始的边界体积是3(长)×4(高)=12
--->然后我们固定以短的边界(高为4的)为一条边,与其他线(5,2,6...)组成一个容器,
--->我们会得到一个规律:那就是在一个区间中,固定使用短的那一条线为一条边,以其它的线为另外一条边,得到的容器体积一定是小于我们一开始(边界体积)的体积的
证明:主要是利用了木桶效应,容积取决于短的板
--->然后我们就可以用这个为跳板来推到整个大的区间
---->先来个整体的实现思路
定义两个指针,一个指向头,一个指向尾,此时可以得到一个体积(边界体积),记录下来,
这个时候就可以利用到上面的规律了,短的那一端指针可以舍弃了,因为以他为边,去和其他线匹配,都小于一开始的体积(边界体积·)
--->接下来让短的那一端的指针++或--(左边++,右边--)
得到下一个边界(left,right),然后记录这个边界体积,然后重复上述步骤,直到两个指针相遇
最后我们求我们得到的边界体积中的最大值即可
--->解释一下为什么,
从一开始的边界,我们根据规律把短的那一条边的匹配(与区间内的其它线组成容器)给省略了,因为都小于边界体积
然后让短的指针--或++
--->因为是一次走一步,,每次去掉一根线,当指针相遇的时候,它们一定走过了所有的线,即我们每次去掉的线都和其他线匹配过了(只是因为规律,我们没有算而已,但是它一定小于边界)
--->这里我们可能会想,若左边的指针在2下标处,而右边的指针在6下标处(做个假设),此时要把右下标舍弃--,那么右边下标跟边界里面的匹配肯定小,但是右边的线还没有跟2下标之前的匹配过呢,你就省略了,是不是漏了
--->其实没有漏,你想啊,你的left是怎么走到2下标的,
是不是也是把1,8当做了短的,然后舍弃过了,既然当做过短的,那么1,和8有没有和right匹配过?肯定的啊,所以之前就匹配过了,也是向内匹配,小于边界值,而边界值已经被记录了,所以不用考虑了