赞
踩
给定 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
要计算结果的实际上是“面积”。所以,我们就需要底和高。设l为左边高度,r为右边高度,输入数组为num,那么目标长方形的高h为num[l]和num[r]的最小值,和中间数据无关;目标长方形的底b就是(r-l)了。
于是问题转换为在输入数组中寻找Min(num[l],num[r])*(r-l)的最大值。
我是这样解决的:固定底长b,寻找以b为底的长方形的最高值,将其存在数组中;然后计算出最大值;
代码实现如下:
public int maxArea(int[] height) { int bottomMaxWidth=height.length; int[] maxHeights=new int[bottomMaxWidth];//比实际的长度多一,为了计算方便 int currentHeight,currentMax,currentCapacity,maxCapacity=-1; for(int i=0;i<height.length;i++){ for(int j=i+1;j<height.length;j++){ currentHeight=Math.min(height[j],height[i]);//获得当前矩形的高 currentMax=maxHeights[j-i];//获得目前以j-i为底长的矩形的最大的高 if(currentMax<currentHeight){ maxHeights[j-i]=currentHeight;//更新 } } } for(int i=1;i<bottomMaxWidth;i++){ currentCapacity=i*maxHeights[i];//计算 if(currentCapacity>maxCapacity){ maxCapacity=currentCapacity;//更新最大值 } } return maxCapacity; }
实际上,算是暴力解法(算出所有可能的容量,然后找出最大值)的一点点升级吧:所谓升级是我们没有挨个计算面积,而是缓存对应的最大高度。时间复杂度n^2,空间复杂度n。
该方式当初是超时了的,但是现在提交的时候(486ms),竟然又可以通过了(LeetCode中文网站)。击败13%左右的用户;
public int maxArea(int[] height) {
int maxarea = 0, l = 0, r = height.length - 1;
while (l < r){
maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
if (height[l] < height[r])
l++;
else
r--;
}
return maxarea;
}
时间复杂度n,空间复杂度1
时间大概在6ms左右!
该方法的解题思路和我通过分析得到的思路是一致的:寻找Min(l,r)*(r-l)的最大值。 我们把该值称为目标表达式。但是思路的实现却截然不同。
优秀解法使用了“双指针遍历”的技巧——所谓“双指针遍历”是指从两个指针分别从数组的左右两端开始向中间靠拢,并在靠拢的过程中,完成数组遍历。
我们可以看到,每次针对一组(left,right),都运算了一遍目标表达式,并且更新其最大值,也就是我们要求的结果。之后便移动指针:每次移动高度较小的指针。
当l和r相遇,数组遍历结束,获得目标值。
这里,有两个关键问题需要想明白:
这两个问题的解答才是这道题的精髓所在!读者可以先思考思考~
首先,我们要明白以下几个定论:
以上三条,看似是“废话”,实则不然;
**对于第一个问题:因为移动高指针后,新得到的矩形面积将只会变小!也就是我们的计算过程并不能捕捉到最优解。**证明如下:
假设left<right,并且移动了right,记此时right指针为current right。如果 current right表示的高度大于left表示的高度,那么目标矩形的面积因为高度h(取决于left,因为left小嘛)没变,底却变小(因为向中心移动了right嘛)而变小;于是只要移动,就变小。
当left>right而移动left时,道理是一样的。通俗来说,就是移动高指针无法得到答案,所以不移动高指针。
**对于第二个问题:主观来讲,因为移动之后,虽然底变小了,但是因为高度存在变大的可能,所以面积也存在变大的可能,即做法目测是合理的;但是,我们就一定能发现最大值吗?答案是:我们一定会发现。**证明如下:
我们需要注意到:记bottom=right-left。当移动指针后,bottom值就不会再出现——不管是left增大还是right减小,bottom总是变小的。
而从自己的“暴力”解法来看,bottom为某个特定值的矩形实际上有很多,比如(1,2)、(3,4)都是bottom为1的矩形,按照“双指针”遍历这样的操作,真的可以用一个值来代替一系列值吗(指一系列bottom相同的矩形的面积)?
实际上,这是我面对该答案最大的疑惑。解决该疑惑后,就会找到第二个问题的答案~
为了分析方便,我们记此时的计算区间为[left,right];bottom=right-left;输入数组为h,并且h[left]<h[right],即下一次将往右移动left指针,面积为A;移动后,区间变为[left+1,right],面积变为B;
我们说,[left+1,right]代表了长度为bottom-1所有的矩形,那么我们先看看[left,right-1]的矩形B1的面积(它们的底长相同);此时,不论h[right-1]的值为多少,我们知道B1都不是我们要找的最大值:
由上面的分析我们可以得到,是A排除了B1,B1的出局和B没有关系,即便B1可能大于B,但是不可能大于A,由第三条定论我们可以知道,B1不需要考虑;
看完比较特殊的例子后,我们看看一般的情况:
我们知道,对于L1,L2,如果L2>L1,那么一定存在某个Rx,h(Rx)>h(L1),即让L1向右移动,这样L才能取到L2;对于R来说也是一样的:如果R1<R2,那么一定存在某个Lx,h(Lx)>h(R1);
由以上结论,可以很方便的得到:对于某个区间[L,R],如果L1<L,那么一定存在Rx,Rx>=R(也就是Rx在R的右边或者就是R本身),且h(Rx)>h(L1);——结论1
Min(a,b)<=a——结论2;
好啦,准备工作完毕!开始证明:在双指针遍历的过程中,如果[l,r]出现,那么其他任何bottom为r-l的矩形,不可能是最大值。
即[l-i,r-i]一定不是最大值。
于是两个问题,均被解决;
需要注意的是,我们在暴力求解的过程中,根据底边长的不同,通过一个数组来缓存最大值,从而简化了一点点暴力求解;(实际上是用空间换时间的做法);
但是在优秀解法中,我们通过证明,当[l,r]出现时,就排除了所有bottom=r-l的矩形,而通过while循环,则对所有bottom的可能进行了遍历;真的很高明;
我也只是理解了这种解法,想是想不出来的;但是我可以把它记在心里写到小本本里啊。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。