盛最多水的容器（Go语言初级例题）

题目分析：

1. 如何计算这个容器能盛多少水？
2. 怎么来判断他是不是最大容器？

如果仅仅从以上这两个问题你可能第一想法就是暴力算法，用两个for循环把所有可能依次遍历找出最大即可，但是如果我给你这个条件呢？

如果用暴力算法用时将会十分巨大。

而这道题最优解是双指针，也是面试经典问题。

如果你看过我之前的找到无重复最长子串，里面同样用到了双指针的想法。

ok我们现在用双指针的思想看这道题。

一目了然，我们需要将左边界和右边界作为两个指针。这里我们需要将双指针初始化为数组的边界，先考虑宽度最大容器，这是潜在的最大容器。然后不断向里缩小通过寻找更高边界来补偿宽度损失。

如果我们从其他地方初始化，我们不知道该向左还是向右扩展，而且思路也不明确。

而容器高度则类似木桶效应，找到两边最短即可。这样我们就能将容器容量表达式写出来。

接下来才是这道题的关键之处！

我们要如何利用双指针来遍历或者说找到最优解？

这就涉及到贪心算法，也是每个码农必须要了解的知识。

"眼前最优，不顾全局" - 在每个决策点都选择当前看起来最好的选项，而不考虑这个选择对未来的影响，它希望通过一系列的局部最优选择，最终达到全局最优解。

就拿这道题目来说：

我们开始以left为左边界，right为右边界，min(height[left],height[right])为高。

下一步我们应该怎么办？

将右边界向左缩还是将左边界向右缩？

我们需要看看那边影响了这个容器的高度，也就是说找到min(height[left],height[right])。

如果他是左边界我们就要向右边移动，left++

看看下一个边界对应的高和新的容量，也就是然后不断向里缩小通过寻找更高边界来补偿宽度损失。

我们就得到了：

代码很好理解，但是为什么这样就能找到最大容器？

这便是贪心算法的优势和精妙之处。

我们直接上图

我们第一次初始化的面积为阴影部分，不难看出这个面积并不大

而左边的高度很大影响了容器，我们left++

这样我们就优化了当前解，当然遍历依旧没有完成，我们还需要执行之前步骤。

同理我们继续直到找到最大容器。

那么有些人就有疑问，会不会漏掉最优解呢？

其实并不会，这也就是这个算法的绝妙之处。也是贪心算法局部最优到全局最优的体现，至于证明需要数学知识，简单来说就是所有被排除的容器（以短木板 i 为边界的）都被数学证明是更差的，而移动短指针是寻找更优解的唯一步骤。

于是我们就得到了完整代码。