每日一题:LeetCode-11.盛水最多的容器

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

每日一题系列(day 13)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,拾取经验,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️


题目:

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

示例:

每日一题:LeetCode-11.盛水最多的容器,每日一题,leetcode,算法,职场和发展

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104
  • 说明:你不能倾斜容器。

思路:

  首先,我们可以使用暴力解法,两层for循环枚举所有情况,枚举完所有情况将最大的值返回即可。
  但是我们的暴力解法时间复杂度是比较高的,对于这题来说,暴力解法应该是不能通过的,有兴趣的小伙伴可以自己尝试。

  我们观察示例,其实不难看出,这题我们可以使用双指针来解决:双指针解决的问题:
  1、首先,我们可以先设置两个指针left,right,一个指向数组的首元素下标,一个指向数组,我们在设置一个max变量,用来记录容器的最大体积。
  2、我们按照题目,设置一个局部变量v用来表示当前体积,然后比较当前体积v与最大体积max,返回两个数中的较大值。
  3、接着,如果左指针指向的值小于右指针指向的值,那么就将左指针右移,反之我们将右指针左移。
  4、有人可能会问,这样遍历的方式并不会将所有的情况枚举出来,那么还能保证正确性吗?举个例子,我们最开始的时候,左边和最右边可以得到一个体积v,而如果让比较小的那个指针向两指针区间枚举,这个得到的体积一定是小于原有的v的,同理,右指针也是如此:每日一题:LeetCode-11.盛水最多的容器,每日一题,leetcode,算法,职场和发展
  5、接下来我们就一直进行循环即可,最后得到的max值就是最大的蓄水池体积。

每日一题:LeetCode-11.盛水最多的容器,每日一题,leetcode,算法,职场和发展

代码实现:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;//ret为最大的体积
        while(left < right)//两指针相遇即结束
        {
            int v = min(height[left], height[right]) * (right - left);//将本次的体积算出来
            ret = max(v, ret);//与之前保存的最大体积比较,如果大于最大体积则刷新ret,否则ret不变

            if(height[left] < height[right]) left++;//哪个指针较小我们就移动哪个指针
            else right--;
        }
        return ret;//最后返回最大体积即可
    }
};

每日一题:LeetCode-11.盛水最多的容器,每日一题,leetcode,算法,职场和发展


  其实这题的双指针写法很难想,只能说多做,累积经验,这类型的题目接触多了或许就可以秒杀,反正我是做不到。文章来源地址https://www.toymoban.com/news/detail-772013.html

到了这里,关于每日一题:LeetCode-11.盛水最多的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(41)
  • 2023/07/11_leetcode每日一题_16. 最接近的三数之和

    给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 和三数之和那道题一样,排序加双指针

    2024年02月15日
    浏览(62)
  • leetcode每日一题44

    图论 dfs/bfs dfs代码框架 思路:本题要求找到被x围绕的陆地,所以边界的陆地O肯定不符合条件。那么我们只要从周边找到陆地O然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地O都变成A,然后再去重新遍历地图的时候,把剩下的O变成X,再把所有的A变成O。 确认递归函数,参数

    2024年01月19日
    浏览(45)
  • 每日一题:leetcode 57 插入区间

    给你一个  无重叠的  , 按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 104 intervals[i].length == 2 0 = int

    2024年02月11日
    浏览(46)
  • 【每日一题】Leetcode - 283. 移动零

    Leetcode - 283. 移动零 从右向左遍历,遇到0,就将后面所有元素前移,同时更新长度,使其减1,因为移动n次,倒数n位就被0占据,后续操作可忽略 前面的操作,从右向左,每次遇到0移动都要跑半个数组,慢在整体前移; 换个思路,从左向右,记录首个0的位置,将后面的第一

    2024年02月11日
    浏览(45)
  • 【LeetCode每日一题】——566.重塑矩阵

    矩阵 简单 566.重塑矩阵 在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同(r x c)的新矩阵,但保留其原始数据。 给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。 重构后

    2024年02月14日
    浏览(47)
  • 【LeetCode每日一题】——575.分糖果

    哈希表 简单 575.分糖果 Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。 医生建议 Alice 要少摄入糖分,只吃掉她所有糖的 n / 2 即可(n 是一个偶数)。Alice 非常喜欢这些糖,她想要在遵循医生建议的情况下,尽可

    2024年02月13日
    浏览(76)
  • 【LeetCode每日一题】——85.最大矩形

    矩阵 困难 85.最大矩形 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例 1: 输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“

    2024年02月13日
    浏览(41)
  • 【LeetCode】每日一题:移除元素

    目录  题目: 思想1:暴力解法 思想2:创建一个temp数组  思想3:双指针 👻内容专栏:《LeetCode刷题专栏》 🐨本文概括: 27.移除元素 🐼本文作者:花 碟 🐸发布时间:2023.4.15 https://leetcode.cn/problems/remove-element/   点击跳转到LeetCode平台OJ页面(27.移除元素)  👉 示例1: 解

    2023年04月19日
    浏览(73)
  • LeetCode每日一题之 复写0

    目录 题目介绍: 算法原理: 特殊位置处理: 代码实现: 题目链接:. - 力扣(LeetCode) 这种对数组元素进行修改,移动的题目我们仍然可以使用双指针法,不过我们按照常规思路从左到右处理数组,不难发现如下这种问题: 当cur指向1时,让dest下一个元素复写cur指向的元素

    2024年04月23日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包