wordpress怎么做下载页,百度seo服务公司,营销型网站案例展示,效果图网站建设目录
题目#xff1a;盛最多水的容器
1. 题目解析
2. 算法原理
3. 代码实现 题目#xff1a;盛最多水的容器
1. 题目解析
题目截图: 如图所示#xff1a; 水的高度一定是由较低的那条线的高度决定的#xff1a;例1图中#xff0c;是由7决定的#xff0c;然后求出…
目录
题目盛最多水的容器
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(vectorint 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;}
};
提交结果 制作不易,若有不足之处或出问题的地方请各位大佬多多指教 感谢大家的阅读支持
