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

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

每日一题系列(day 13)

前言:

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

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


题目:

  给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

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

返回容器可以储存的最大水量。

示例:

提示:

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

思路:

  首先,我们可以使用暴力解法,两层for循环枚举所有情况,枚举完所有情况将最大的值返回即可。

  但是我们的暴力解法时间复杂度是比较高的,对于这题来说,暴力解法应该是不能通过的,有兴趣的小伙伴可以自己尝试。

  我们观察示例,其实不难看出,这题我们可以使用双指针来解决:双指针解决的问题:

  1、首先,我们可以先设置两个指针left,right,一个指向数组的首元素下标,一个指向数组,我们在设置一个max变量,用来记录容器的最大体积。

  2、我们按照题目,设置一个局部变量v用来表示当前体积,然后比较当前体积v与最大体积max,返回两个数中的较大值。

  3、接着,如果左指针指向的值小于右指针指向的值,那么就将左指针右移,反之我们将右指针左移。

  4、有人可能会问,这样遍历的方式并不会将所有的情况枚举出来,那么还能保证正确性吗?举个例子,我们最开始的时候,左边和最右边可以得到一个体积v,而如果让比较小的那个指针向两指针区间枚举,这个得到的体积一定是小于原有的v的,同理,右指针也是如此:

  5、接下来我们就一直进行循环即可,最后得到的max值就是最大的蓄水池体积。

代码实现:

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;//最后返回最大体积即可
    }
};


  其实这题的双指针写法很难想,只能说多做,累积经验,这类型的题目接触多了或许就可以秒杀,反正我是做不到。

相关文章
|
2月前
|
容器
Leetcode第十一题(盛最多水的容器)
LeetCode第十一题要求找出两条线,使得它们与x轴构成的容器能盛最多的水,通常使用双指针法来解决,通过移动较短的一边来尝试增加容量。
14 0
Leetcode第十一题(盛最多水的容器)
|
4月前
|
算法 容器
LeetCode第11题盛最多水的容器
该文章介绍了 LeetCode 第 11 题盛最多水的容器的解法,通过分析得出只能移动短板才可能使面积变大的规律,使用双指针法解决该问题,避免了穷举法的高时间复杂度,并总结了算法题需要多实践、思考和积累技巧来提升解题能力。
LeetCode第11题盛最多水的容器
|
4月前
|
Python 容器
【Leetcode刷题Python】11. 盛最多水的容器
解决LeetCode "盛最多水的容器" 问题的Python实现代码,使用了双指针的方法来找出能够容纳最多水的两条线。代码中定义了两个指针i和j,分别从数组的两端向中间遍历,通过计算两个指针所指高度的较小值与它们之间的距离的乘积来更新最大面积res。
31 0
|
6月前
|
算法 测试技术 程序员
力扣经典150题解析之二十八:盛最多水的容器
力扣经典150题解析之二十八:盛最多水的容器
45 0
|
6月前
|
算法 容器
【LeetCode刷题】快乐数、盛水最多的容器
【LeetCode刷题】快乐数、盛水最多的容器
|
6月前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
|
7月前
|
容器
leetcode代码记录(盛最多水的容器
leetcode代码记录(盛最多水的容器
30 1
|
7月前
|
算法 容器
【优选算法】—Leetcode—11—— 盛最多水的容器
【优选算法】—Leetcode—11—— 盛最多水的容器
|
7月前
|
容器
【力扣】11. 盛最多水的容器
【力扣】11. 盛最多水的容器