【边学边敲边记】LeetCode010:盛最多水的容器
一、写在前面
LeetCode 第九题删除排序数组中的重复项传输门：LeetCode009: 删除排序数组中的重复项
今天给大家分享的是LeetCode 数组与字符串 第十题：盛最多水的容器，为面试而生，期待你的加入。
二、今日题目
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图例
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
三、 分析
第一眼看到这个图，我就觉得，这个题目应该很有意思，beautiful。
刚看完题目，第一想法是直接遍历，求出每对值的构成的元素面积，然后取出最大值，O(n^2)的时间复杂度，想想都有些复杂，“傻”，于是放弃这样思考，夹逼准则，上一个题目就有读者提出来能不能用夹逼准则，我的回答是不能，这题，我们能，基本思路如下图所示：
我的思想
四、解题
我的方法：
夹逼法，我们不止一次用到。
时间复杂度控制再：O(n)
空间复杂度：O(1)
夹逼方法
提交结果
提交结果
测试数据：50组
运行时间：36-64ms
击败人百分比:15.52-95.79%
代码优化一下：
优化
在上面的优化中只是单纯的缩减了代码的数量，这里用到了一些Python的小知识，我目前也在巩固Python基础知识，感兴趣可以点击这里查看。
在代码变简洁的同时，我们由于调用Python的库，简便操作，使时间效率有所降低。
提交结果
提交结果
测试数据：50组
运行时间：48-88ms
击败人百分比:5.64-37.70%
五、疑惑
简单介绍夹逼准则
和大家普及一个知识，夹逼定理英文原名Squeeze Theorem。也称两边夹定理、夹逼准则、夹挤定理、挟挤定理、三明治定理，是判定极限存在的两个准则之一，是函数极限的定理。
从上面可以看出，夹逼准则是数学里的一个方法，所以算法要好，脑袋灵活，数学是必不可少的，我们找最大值，最小值，其实就是一个找极值的过程，和一般我们初中高中接触到的数学不同的是，这里的数据是离散的，所以我们得定点分析。
夹逼准则定理
为了日后机器学习，深度学习，我们普及一下夹逼准则：
1.如果数列{Xn},{Yn}及{Zn}满足下列条件：
（1）当n>N0时，其中N0∈N*，有Yn≤Xn≤Zn，
（2）{Yn}、{Zn}有相同的极限a，设-∞<a<+∞；
则，数列{Xn}的极限存在，且当 n→+∞，limXn =a。
2.函数A>B,函数B>C，函数A的极限是X，函数C的极限也是X ，那么函数B的极限就一定是X，这个就是夹逼定理。
夹逼准则应用
1.设{Xn}，{Zn}为收敛数列，且：当n趋于无穷大时，数列{Xn}，{Zn}的极限均为：a.
若存在N，使得当n>N时，都有Xn≤Yn≤Zn,则数列{Yn}收敛，且极限为a.
2.夹逼准则适用于求解无法直接用极限运算法则求极限的函数极限，间接通过求得F(x)和G(x)的极限来确定f(x)的极限。
以上部分内容来自百度百科，苦海无涯，好好学习。
六、结语
坚持 and 努力 ： 终有所获
往期精彩
进学习交流群
不失联，扫码加X先生微信学习交流
温馨提示
欢迎大家转载，转发，留言，点赞支持X先生。
文末广告点一下也是对X先生莫大的支持。
做知识的传播者，随手转发。
苦海无涯，赞赏一下