C++ 优先算法——盛最多水的容器（双指针）

目录

题目：盛最多水的容器 

1. 题目解析

2. 算法原理

3. 代码实现

---

题目：盛最多水的容器 

1. 题目解析

题目截图:

如图所示：

水的高度一定是由较低的那条线的高度决定的：例1图中，是由7决定的，然后求出8和7它们对应的下标的之间的差，再进行相乘就得出体积。

题目的意思就是要我们找出一个数组中，两个下标对应的值，取它较小的那个值，并与两个下标之差的乘积，找出这个最大的乘积。

我们挑一组验证一下，题目给的结果是不是最大的

2. 算法原理

这道题有两种解法：

1. 暴力枚举
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;}
};

提交结果：

制作不易,若有不足之处或出问题的地方，请各位大佬多多指教 ，感谢大家的阅读支持！！！