两边夹的应用三

用户头像
孙苏勇
关注
发布于: 2020 年 05 月 21 日
两边夹的应用三

​对于两边夹的应用,这个主题之前写过两篇,今天这篇继续该系列。



题目可参见leetcode第11题,给定一组非负整数组成的数组,下标表示位置,数值表示位置的高度,求其中两个高度之间能储水的最大值,如题图所示。



先分析一下题目中储水量的求法,从图中可以看出,储水量可以理解为求蓝色部分的面积,也就可以转化为求矩形的面积,而矩形的宽为右下标减去左边下标的差值,而矩形的高是左右两边高度较小的一边,可得求解面积公式如下:



area = min(leftHeight, rightHeight) * (rightIndex - leftIndex)



知道了面积求法后,重点变成如何确定哪两个坐标间计算出的面积最大,如果用暴力求解的话,相当于每个坐标都要和其后续坐标求解一次,其时间复杂度为(n-1)*n/2,即O(n^2)。



现在我们同样以两边夹的方式考虑该问题,则计算方式可以按如下流程:

1、初始化左右指针为leftIndex为0, rightIndex为n-1(即数组的第一个和最后一个下标),最大面积area为0;

2、当leftIndex < rightIndex,做如下计算;

3、用面积公式求当前面积,并与当前最大面积相比较以决定是否更新最大面积,公式如下:

area = max(area, min(leftHeight, rightHeight) * (rightIndex - leftIndex))

4、更新左右指针,规则如下,如果leftHeight <= rightHeight,leftIndex++,否则rightIndex--,继续步骤2,直至条件不满足,执行5;

5、此时返回的area即为最大面积。



该计算过程最核心的步骤是第4步,如何更新左右指针。采用第4步所描述的方式,主要原因是,如果想让下一次的面积更大,只有保留当前较高的一边,让矮的一边移动以寻求更高的高度,才有可能得到更大的面积。如果移动较高的一边,则下一次的面积必然是减少的,不难理解,高度仍是较低的高度,而宽又减少了1。

​采用两边夹的方式需要计算n-1次,时间复杂度为O(n)。该计算过程用图来表示应该更好理解,所以画了如下示意图来简单表示该计算过程,图示仅演示了初始的几个步骤,剩余步骤方法相同,如下所示:



过程讲清楚了,就上代码吧:

public int maxArea(int[] height) {
if (null == height || height.length < 2) {
return 0;
}
int leftIndex = 0, rightIndex = height.length - 1;
int area = 0;
while (leftIndex < rightIndex) {
area = Math.max(area, Math.min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex));
if (height[leftIndex] < height[rightIndex]) {
leftIndex++;
} else {
rightIndex--;
}
}
return area;
}



对于这个题目如果我们改个条件,要求计算最大值,并且返回相应的左右位置坐标,甚至可能不只一组坐标符合条件,要求返回最大值及所有的坐标组合,这就当对该题目的一个延伸,大家有兴趣可以实现一下​。



该系列其他文章:

两边夹的应用二

两边夹的应用





发布于: 2020 年 05 月 21 日 阅读数: 37
用户头像

孙苏勇

关注

不读书,思想就会停止。 2018.04.05 加入

公众号“像什么",记录想记录的。

评论

发布
暂无评论
两边夹的应用三