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 努力 ： 终有所获。

欢迎大家关注微信公众号：极简XksA,获取Python/Java/前端等学习资源！