本文主要是介绍力扣最热一百题——盛水最多的容器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
终于又来了。我的算法记录的文章已经很久没有更新了。为什么呢?
这段时间都在更新有关python的文章,有对python感兴趣的朋友可以在主页找到。
但是这也并不是主要的原因
在10月5号我发布了我的第一篇博客,大家也可以看见我的每一篇算法博客的开头都是吾日三省吾身,比那个男人帅吗?比那个男人爱她吗?比那个男人有实力吗?也可以在我的文章中的比如代码注释,结语感想看见一些emo 的句子
在之后的文章不会出现了。因为我已经彻底的失去了所爱的那个她,彻底失去。她的言语刺痛了我,剥夺了我的爱。
但是,流程该走还是要走,那就进入新的流程吧!
一身正气报国家,旁无乱境不恋她
ヾ(◍°∇°◍)ノ゙
力扣题号:11. 盛最多水的容器 - 力扣(LeetCode)
下述题目描述和示例均来自力扣
题目描述
给定一个长度为
n
的整数数组height
。有n
条垂线,第i
条线的两个端点是(i, 0)
和(i, height[i])
。找出其中的两条线,使得它们与
x
轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例
示例 1:
输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。示例 2:
输入:height = [1,1] 输出:1提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
回归文章第一弹就不搞这些虚的了。直接上嘴脸!
思路
其实就是要找到这里面,两个柱子包起来里面的最大的面积对吧。
第一种思路就是直接暴力for循环,把每一个都找一遍,然后返回最大的那一个。我在这里就不演示暴力的解法了,盲猜跑不出来(反正我没试过♪(^∇^*))。
然后就是第二章思路,在数组里面优化是不是第一时间想到的就是双指针呐(*^▽^*)!对喽~~
我们直接定义左右指针,然后精华是什么呢?什么时候移动指针呢?
答:
在每一次判断的时候,那个指针所对应的高度低,就移动谁,left是++,right是--,你想嘛。这里装水的高度根据木桶效应是取决于最低的那一个的,如果你移动的是更低的那一个,那么即使右更高的,也没有用,而且底边长还会更低,对吧,那就是这个思路,代码如下:
Java解法没有之一:双指针
详细的代码注释也有
class Solution {public int maxArea(int[] height) {// 利用双指针int left = 0;int right = height.length - 1;// 开始循环判断// 在这里的时候,left == right是没有用的,所以直接 < 即可int result = 0;while (left < right) {// 底边长度为right - leftint b_len = right - left;// 高度是他们之间最小的那一个// 这里每次固定移动高度较低的那一边int h_len = height[left] < height[right] ? height[left++] : height[right--];// 获取面积int area = b_len * h_len;// 大于result就刷新值if (area > result) {result = b_len * h_len;}}return result;}
}
就是快
因为很多同学也是使用C++,和Python的,所以我今后也同时提供C++和python的语法
C++解法没有之一:双指针
class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size()- 1;int result = 0;while(left < right){int b_len = right - left;int h_len = height[left] < height[right] ? height[left++] : height[right--];int area = b_len * h_len;if(area > result){result = area;}}return result;}
};
??????????????????????????????????????????????????????????????????????????????????????????????????
我没看错吧,C++要花60ms,Java只需要2ms,wdf?
Python解法之没有之一:双指针
class Solution:def maxArea(self, height: List[int]) -> int:left = 0right = len(height) - 1result = 0while left < right:b_len = right - lefth_len = height[left] if height[left] < height[right] else height[right]if height[left] < height[right]:left += 1else:right -= 1area = b_len * h_lenif area > result:result = areareturn result
怎么说捏,python更慢我是理解的,C++比Java慢那么多我不理解
结语
咋说捏~!~
C++和Java用同一个方法
C++比Java慢,emmmmmmmmmmmmmmmmmmmmmmmmmmmm
不理解
那我直接得出结论
Java是这个世界上最好的语言~!!!!!!!!!!!
再见┏(^0^)┛
这篇关于力扣最热一百题——盛水最多的容器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!