Leetcode打卡 | No.011 盛最多水的容器

写在前边：

欢迎和小詹一起定期刷leetcode，每周一和周五更新一题，每一题都吃透，欢迎一题多解，寻找最优解！这个记录帖哪怕只有一个读者，小詹也会坚持刷下去的！

ＰＳ：从第１０期开始，代码以图片形式给出，方便手机用户阅读，避免左右滑不便阅读，完整代码会上传ＱＱ群【７４４５０８６００】，当期同步分享到微信群。

No.11 盛最多水的容器

原题：

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 注意：你不能倾斜容器，n 至少是2。【这里返回值返回area面积即可】

题目分析：

这一题可以画一个平面直接坐标系，就显得很清楚啦！关键在于面积的表示！难点在于算法的思路，如何能够提高效率。这一题，只能算中等偏下的难度吧！首先分析下盛最多水是什么意思，也就是如何衡量容器容量！画坐标系如下：

容量，相信所有人都知道底面积乘以高即可。这里又可以理解成木桶效应，决定容量的高取决于短板！哲理噢小伙伴们！这里的容量就可以用面积来衡量，用公式表示即：

area = (j-i)*min(height[i],height[j])

方法一：暴力法！两层循环遍历所有可能，返回最大面积即可！做过太多类似的就不具体介绍 。代码如下：

然而，测试可行，提交发现有些样例无法通过，会超时噢：

原因你懂得！两层循环遍历所有的可能，计算量很大噢。有这样一种双指针的方法，分别指向列表的两端，逐步向中间逼近，最后返回最大值。而逼近的方法是较高的那头不动，较低的那头向高的那头移动（向大佬低头！）原因很容易理解哈。代码实现如下，解释见代码注释：

这种方法效果还不错，可以吃鸡噢！