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不會更新最優解。

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

代碼