Leetcode 11 - Container With Most Water（two pointers）

github仓库：https://github.com/lzed/leetcode

题意

给定一堆竖着的线，找两条线，使这两条线围城的容器的面积最大。

思路

首先，我们先贪心的去考虑：假设我们直接取最两边的两条线i和j，能否获得最大高度？显然是不一定的。

然后，我们去需要取移动两边的选取i和j了。

然后基于如下事实：

若ai<aj$a_i ，那么我们向左移动j不会更新最优解。因为此时的面积<nobr>S=ai(j−i)</nobr><script type="math/tex" id="MathJax-Element-2">S = a_i(j - i)$，并且若向左移动j到k的位置，那么此时的面积S′=min(ai,ak)(k−i)$S' = min(a_i, a_k)(k - i)$。

若ai>aj$a_i > a_j$，那么我们向右移动i不会更新最优解。

所以，就可以得到我们的算法：

代码