今天的新闻有哪些,沈阳网站的优化,企业网站的在线推广方法有哪些,做动画 的 网站有哪些软件Problem: 11. 盛最多水的容器 文章目录 题目解析算法原理讲解复杂度Code 题目解析 首先我们来解析一下本题 题目中说到#xff0c;要找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。
那我们现在来看最外侧的两根#xff0c;一个高度为8#… Problem: 11. 盛最多水的容器 文章目录 题目解析算法原理讲解复杂度Code 题目解析 首先我们来解析一下本题 题目中说到要找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
那我们现在来看最外侧的两根一个高度为8一个则为7那我们肯定选择高度为7的如果选择8的话就会出现溢出的问题我们这里要求解的是可以容纳多少的水分所以便要计算的是【容量】那从第一根柱子到第八根的距离是多少呢即8 - 1 7所以最后的容量即为7 * 7 49 那我们再来看一个高度取小的那个为6宽度则取4所以最后的容积为4 * 6 24比49要来的小但我们要取的是最大的那一个容量所以还是取 49 所以对于本题来说我们初步的想法就是不断地去找两根柱子然后计算出这两根柱子之间的所围成的容积大小最后我们所要的则是最大的那一个容积
算法原理讲解 接下去呢我们再来讲解一下本题的算法原理 首先的话来讲解一下第一种方法那就是我们同学最喜欢使用的【暴力枚举】因为我们是不断地一一比较所以直接使用双层for循环去进行实现即可。不过呢这种写法我试了一下是会超时的所以立马放弃❌ 接下去第二种也是我要进行重点讲解的那利用单调性然后使用【双指针】来进行求解。因为我们在对两根柱子不断进行比较的时候数字都会不停地发生变化那么这里就会有两个情况 第一种呢是比较的数字开始出现缩减的情况即w变小而且距离也开始缩减即h变小那w和h都进行缩减的话最后的乘积[v]也会变得小第二种的话则是所计算的数据不变新的数据发生了放大所以呢h不会缩小不过距离的话还是会发生缩减此时整体[v]也会变得小 那根据上面的分析我们呢可以使用双指针去模拟遍历两个x轴的数据 看到下面我们直接从两侧开始进行计算那么在计算完得出第一个容量v1后我们便可以直接舍弃这个【1】因为其再与任何结合计算都会比【1】与【7】要来得小原因在于距离会发生一个缩减 那接下去还是一样的思路我们在使用双指针进行遍历的时候只需要去判断二者的大小即可左侧小的话就右移右侧小的话就左移然后记录下每一个容量v1、v2、v3最后的话再去做一个比较即可 复杂度
时间复杂度: 对于时间复杂度而言因为我们就是使用左右指针在遍历原先的数组所以呢复杂度即为 O ( n ) O(n) O(n) 空间复杂度: 因为没开辟多余的空间所以空间复杂度, 示例 O ( 1 ) O(1) O(1) Code 以下是代码展示读者可以根据我上面所分析的思路自行去书写一下代码 可以看到我在这里定义两个左右指针left和right然后呢通过循环去遍历并计算它们两个位子上的数计算的方法就是我们上面所讲记住要去不断地更新最大值当一轮计算完成之后不要忘记去更新left和right。最后当这个循环结束再去返回计算出来的最大值即可。
class Solution {
public:int maxArea(vectorint height) {int left 0, right height.size() - 1;int ret 0;while(left right){int v min(height[left], height[right]) * (right - left);ret max(v, ret); // 更新最大值if(height[left] height[right]) left;else right--;}return ret;}
};
