每日一题系列(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;//最后返回最大体积即可
}
};
文章来源:https://www.toymoban.com/news/detail-772013.html
其实这题的双指针写法很难想,只能说多做,累积经验,这类型的题目接触多了或许就可以秒杀,反正我是做不到。文章来源地址https://www.toymoban.com/news/detail-772013.html
到了这里,关于每日一题:LeetCode-11.盛水最多的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!