目录
题目:盛最多水的容器
1. 题目解析
2. 算法原理
3. 代码实现
题目:盛最多水的容器
1. 题目解析
题目截图:
如图所示:
水的高度一定是由较低的那条线的高度决定的:例1图中,是由7决定的,然后求出8和7它们对应的下标的之间的差,再进行相乘就得出体积。
题目的意思就是要我们找出一个数组中,两个下标对应的值,取它较小的那个值,并与两个下标之差的乘积,找出这个最大的乘积。
我们挑一组验证一下,题目给的结果是不是最大的
2. 算法原理
这道题有两种解法:
- 暴力枚举
- 利用单调性,使用双指针解决问题
这里解决用第二种方法,下来对这个方法进行解释
这样看出,取出的小部分向内 永远都是比第一次的v小,所以我们得出:当选区间最左、最右两个数,算出来一个容器之后,如果拿这个比较小的数向内枚举的话,发现容器是一直减小的,因此上述取的小部分对于4就不用考虑了。所以可以把这个单调性规律推广到整个数组。
然后算出来V1,发现1是较小的,然后就直接让left向后移动,不用再考虑1的向内枚举了
然后重复上面操作进行下去,直到两指针相遇。
我们可以总结一下:
- 向内枚举,w是肯定下降的。(w就是两个下标的差)。
- 若以两条垂线较低的那条向内枚举,那么h的变化情况:下降或不变。所以导致V是一直小于当前最大的V的,所以可以不用考虑。
- 所以谁指向的数较小,谁移动(指针向内移动)。
- 移动完后,继续算出一个容器V。
- 更新max。
- 再接着移动指针,重复上面操作。
- 指针相遇就结束。
所以这里用的还是双指针的方法,左右指针,向内移动,一起遍历整个数组,所以这个算法的时间复杂度是O(N)。
按照上述的逻辑,我们下面实现代码。
3. 代码实现
题目跳转:盛最多水的容器
//这里就是用的上面介绍的双指针法
class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while (left < right) {//用最小的那个当高,并与它们之间相减得出的距离结果相乘int V = min(height[left], height[right]) * (right - left);//每次都更新一下最大的体积ret = max(ret, V);// 移动指针 谁对应的值小谁移动// 注意left与right的移动方向if (height[left] < height[right]) {++left;} else {--right;}}return ret;}
};
提交结果:
制作不易,若有不足之处或出问题的地方,请各位大佬多多指教 ,感谢大家的阅读支持!!!