【算法】双指针求解盛最多水的容器

这篇具有很好参考价值的文章主要介绍了【算法】双指针求解盛最多水的容器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针

Problem: 11. 盛最多水的容器

题目解析

首先我们来解析一下本题

题目中说到,要找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水

  • 那我们现在来看最外侧的两根,一个高度为8,一个则为7,那我们肯定选择高度为7的,如果选择8的话就会出现溢出的问题;我们这里要求解的是可以容纳多少的水分,所以便要计算的是【容量】,那从第一根柱子到第八根的距离是多少呢?即8 - 1 = 7
  • 所以最后的容量即为7 * 7 = 49

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针

  • 那我们再来看一个,高度取小的那个为6,宽度则取4,所以最后的容积为4 * 6 = 24,比49要来的小,但我们要取的是最大的那一个容量,所以还是取 49

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针

💬 所以对于本题来说,我们初步的想法就是不断地去找两根柱子,然后计算出这两根柱子之间的所围成的容积大小,最后我们所要的则是最大的那一个容积

算法原理讲解

接下去呢我们再来讲解一下本题的算法原理

  • 首先的话来讲解一下第一种方法,那就是我们同学最喜欢使用的【暴力枚举】,因为我们是不断地一一比较,所以直接使用双层for循环去进行实现即可。不过呢这种写法我试了一下是会超时的,所以立马放弃❌

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针

  • 接下去第二种,也是我要进行重点讲解的,那利用单调性,然后使用【双指针】来进行求解。因为我们在对两根柱子不断进行比较的时候,数字都会不停地发生变化,那么这里就会有两个情况:
    • 第一种呢是比较的数字开始出现缩减的情况,即w变小;而且距离也开始缩减,即h变小,那wh都进行缩减的话,最后的乘积[v]也会变得小
    • 第二种的话则是所计算的数据不变,新的数据发生了放大,所以呢h不会缩小,不过距离的话还是会发生缩减,此时整体[v]也会变得小

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针

那根据上面的分析,我们呢可以使用双指针去模拟遍历两个x轴的数据

  • 看到下面我们直接从两侧开始进行计算,那么在计算完得出第一个容量v1后,我们便可以直接舍弃这个【1】,因为其再与任何结合计算都会比【1】与【7】要来得小,原因在于距离会发生一个缩减

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针

  • 那接下去还是一样的思路,我们在使用双指针进行遍历的时候,只需要去判断二者的大小即可,左侧小的话就右移,右侧小的话就左移,然后记录下每一个容量v1v2v3,最后的话再去做一个比较即可

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针

复杂度

  • 时间复杂度:

对于时间复杂度而言,因为我们就是使用左右指针在遍历原先的数组,所以呢复杂度即为 O ( n ) O(n) O(n)

  • 空间复杂度:

因为没开辟多余的空间,所以空间复杂度, 示例: O ( 1 ) O(1) O(1)

Code

以下是代码展示,读者可以根据我上面所分析的思路,自行去书写一下代码

  • 可以看到,我在这里定义两个左右指针leftright,然后呢通过循环去遍历并计算它们两个位子上的数,计算的方法就是我们上面所讲,记住要去不断地更新最大值
  • 当一轮计算完成之后不要忘记去更新leftright。最后当这个循环结束再去返回计算出来的最大值即可。
class Solution {
public:
    int maxArea(vector<int>& 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;
    }
};

【算法】双指针求解盛最多水的容器,# 双指针,算法,双指针文章来源地址https://www.toymoban.com/news/detail-674615.html

到了这里,关于【算法】双指针求解盛最多水的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|双指针系列No.4】leetcode11. 盛最多水的容器

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(48)
  • 【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器

    202. 快乐数 https://leetcode.cn/problems/happy-number/ 编写一个算法来判断一个数  n  是不是快乐数。 「快乐数」  定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是  无限循环  但始终变不到 1。 如果这

    2024年02月11日
    浏览(37)
  • 【算法专题--双指针算法】leecode-202. 快乐数(medium)、leecode-11. 盛最多水的容器(medium)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月23日
    浏览(38)
  • 【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字

    盛水最多的容器 (1)暴力解法   算法思路:我们枚举出所有的容器大小,取最大值即可。   容器容积的计算方式:   设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定,因此可得容积公式 :

    2024年02月13日
    浏览(48)
  • 「优选算法刷题」:盛最多水的容器

    给定一个长度为  n  的整数数组  height  。有  n  条垂线,第  i  条线的两个端点是  (i, 0)  和  (i, height[i])  。 找出其中的两条线,使得它们与  x  轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明: 你不能倾斜容器。 示例 1: 示例 2: 这道

    2024年01月19日
    浏览(60)
  • 【力扣算法12】之 11. 盛最多水的容器 python

    给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明 :你不能倾斜容器。 输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂

    2024年02月16日
    浏览(49)
  • 11. 盛最多水的容器

    给定一个长度为  n  的整数数组  height  。有  n  条垂线,第  i  条线的两个端点是  (i, 0)  和  (i, height[i])  。 找出其中的两条线,使得它们与  x  轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明: 你不能倾斜容器。 示例 1: 示例 2: 提示

    2024年01月20日
    浏览(58)
  • 力扣-盛最多水的容器

    11.盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。 说明:你不能倾斜容器 示例1: 示例 2: 分析: 题解

    2024年01月15日
    浏览(41)
  • 力扣 | 11. 盛最多水的容器

    双指针解法–对撞指针

    2024年01月18日
    浏览(40)
  • leetcode 11. 盛最多水的容器

    leetcode 11. 盛最多水的容器 解题思路 :双指针 每次向内移动矮的指针,因为如果向内移动高的指针,面积一定会变小;如果向内移动矮的指针,面积还有可能变大。

    2024年02月06日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包