这次的题目比较简单而且有意思哦～
leetcode11: 盛最多水的容器
题目描述：
给你 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
解题思路:
假设选中两个点 (i, ai) 和 （j, aj) , 则容器的盛水量area = （j-i） * min(ai,aj)。
我们需要做的是从所有可能的盛水量area中找出最大的值。如何才能使盛水量area的值大呢？ 小学的乘法阿姨老师也教过我们：
乘数因子越大，积也就越大。
所以我们要使两点的距离j-i 足够大，两点的最短高度min(ai,aj) 也足够大，盛水量area才能大。
如何枚举每一种可能的盛水量area？
我们可以用暴力搜索的方式，不断固定其中一个点first，遍历组成area的另一点second。这样全部枚举完所有可能性，就能最终找到答案。时间复杂度为O(n^2)。
但是我们并不需要枚举所有的可能，我们只需要从可能更大的area中找结果就好：
从左右两端开始枚举，此时两点的距离second - first最大，再不断往中间靠拢，向中间移动 i和j之间更短的点。当first, second相遇时，就可以选出最大的盛水量area。
- 时间复杂度：O(n)
- 套路：符合双指针的场景，双指针可将暴力搜索的复杂度降低一维。本题从O(n^2) 变为 O(n)
当然没完，这道题有意思在 ：如何证明 每次移动短的指针就一定能枚举到最大的Area呢？我们来看一种 图解的证明方式。
图解证明
结合上面的8根柱子，我们可以看图：
因为
second - first的值不断变小，每次移动短的指针肯定是必选当前短的指针时的最大面积，也就是指针所在行或者列的最大值。所以这种移动方式是一定会 枚举到最大的Area 的。
这种证明方式虽然简单好理解，但是不够严（Z）谨（X）。这道题也可以用数学反证法证明，感兴趣的可私信阿姨交流。
代码很简单：
Java版本
class Solution {
public int maxArea(int[] height) {
int res = 0;
int first = 0,second = height.length -1;
while (first<second){
res = Math.max(res,Math.min(height[first],height[second]) * (second-first));
if(height[first] <= height[second]){
first++;
}else{
second--;
}
}
return res;
}
}
这期就结束了，是不是很意外。233酱其实写好了5道题的大纲，但最终还是放弃了。
我大家很难通过零碎的公众号阅读时间沉浸下来思考5道题，另外图文也略显苍白。
所以关于算法的文章更新，我决定以后会选取一些有意思或者难懂的题目，系统地由题目延伸出特定的数据结构和算法，为大家详解。
小伙伴们有想了解的数据结构算法或者被某道leetcode卡住了，都可以私信233。233会优先考虑这些题材哦～
觉得本文有收获欢迎关注233酱的公众号：「码农知识点」，和我进一步交流～
网友评论