盛最多水的容器，超有意思有技巧的Leetcode题

这是我参与2022首次更文挑战的第14天，活动详情查看：2022首次更文挑战

一、写在前面

LeetCode 第一题两数之和传输门：听说你还在写双层for循环解两数之和？

LeetCode 第二题两数之和传输门：两个排序数组的中位数，“最”有技术含量的解法！

LeetCode 第三题最长回文子串传输门：马拉车算法解最长回文子串！Manacher

LeetCode 第四题字符串转整数 (atoi)：“愚公移山”的方法解atoi，自以为巧妙！

LeetCode 第五题最长公共前缀：继续解Leetcode，最长公共前缀

LeetCode 第六题三数之和：Leetcode“最经典”算法题之一：三数之和

LeetCode 第七题最接近的三数之和：最接近的三数之和，妙

LeetCode 第八题有效的括号：Leetcode有意思的一题：有效的括号

LeetCode 第九题删除排序数组中的重复项：LeetCode之删除排序数组中的重复项

今天给大家分享的是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 努力 ： 终有所获。

点赞 在看 留言 转发 ，四连支持，原创不易。好的，那么下期见，我是爱猫爱技术，更爱思思的老表⁽⁽ଘ( ˙꒳˙ )ଓ⁾⁾