Leetcode 上第 11 號問題：盛最多水的容器，是一道非常經(jīng)典的問題。不久前，一個同學(xué)還告訴我，他去字節(jié)跳動面試，考了一模一樣的原題。

這個問題本身很好理解：在坐標(biāo)軸的每個坐標(biāo)位置都放上了一系列長度不等的豎板。要求在這些豎板中選出兩塊，這兩塊豎板和坐標(biāo)軸組成了一個“容器”。這個容器的底就是這兩塊豎板所在的坐標(biāo)之間的距離；而高則是這兩塊豎板之間的較短者。所謂短板效應(yīng)。

問題是希望找到兩塊豎板，使得這個“容器”的面積最大。

如果總共有 n 塊木板可以選擇的話，我們可以暴力枚舉任意兩塊木板的組合，檢查他們組成的容器面積，一共需要檢查 n * (n - 1) / 2 對木板的組合。

如果會排列組合的同學(xué)，可以很輕易地使用組合公式得到這個結(jié)果，即：

C(n, 2) = n * (n - 1) / 2

即使不擅長排列組合的同學(xué)，也可以非常容易地通過程序來分析出這個結(jié)果。我們的暴力枚舉的程序偽碼是這樣的：（其中數(shù)組 a 存儲了 n 個木板的高度）

res=0; for(i=0;i

在上面的循環(huán)中，res 一共被比較計算了幾次？

可以想象，當(dāng) i == 0 的時候，j 的取值范圍是從 1 到 n-1，內(nèi)循環(huán)一共計算了 n-1 次；

當(dāng) i == 1 的時候，j 的取值范圍是從 2 到 n-1，內(nèi)循環(huán)一共計算了 n-2 次；

當(dāng) i == 2 的時候，j 的取值范圍是從 3 到 n-1，內(nèi)循環(huán)一共計算了 n-3 次；

以此類推...

i 最大取值為 n - 2，此時 j 的取值為 n-1，內(nèi)循環(huán)只計算了 1 次。

所以，整體，內(nèi)循環(huán)計算的次數(shù)，就是 1 + 2 + 3 + ... + (n-3) + (n-2) + (n-1)。

這是一個等差數(shù)列求和，一共 n-1 項，首項為 1，末項為 n-1。帶入等差數(shù)列求和公式，就是 n * (n - 1) / 2。

很顯然，這樣暴力枚舉，我們的算法時間復(fù)雜度是 O(n^2) 級別的。

實際上，這個問題有 O(n) 級別的解法，也就是大名鼎鼎的雙指針解法，思路是這樣的：

首先，使用 left 和 right 兩個指針，分別指向最左邊的木板 a[0] 和最右邊的木板 a[n-1]。這樣，left 和 right 就構(gòu)成了一個容器。這個容器的面積，是我們的初始值。

下一步，我們只需要看 left 對應(yīng)的木板和 right 對應(yīng)的木板誰小，就好了。如果 left 更小，那么就 left ++，也就是下一步去檢查 a[1] 和 a[n - 1] 組成的容器是否更大？如果 right 更小，那么就 right --，也就是看 a[0] 和 a[n - 2] 組成的容器是否更大？這個過程以此類推，如果發(fā)現(xiàn)了更大的容器，就更新結(jié)果。

算法偽碼大概是這樣的：

l=0,r=n-1,res=0; while(l

可以看出來，這個過程，或者 left ++，或者 right --，木板之間的距離越來越小。直到 left 和 right 碰上，也就是兩塊木板重合了，容器的底為 0，此時，算法結(jié)束。

這個算法的復(fù)雜度是 O(n) 的。因為整個算法中，每一個木板都或者被 left 指針指過一次，或者被 right 指針指過一次，直到 left 和 right 匯合。

對應(yīng)的，res 一共被計算了 n-1 次。因為兩個木板才能形成一個容器。使用這種方式，n 個木板，一共組成了 n-1 個容器。

這個算法看起來非常簡單，但是，一個很致命的問題是：這個算法為什么是正確的？

一個直觀的想法是：每次不管是 left 右移，還是 right 左移，容器的底都會減一。由于容器的底減小了，所以，如果我們要想得到更大的面積，就要讓容器的高變大。整個容器的高是由最短的木板決定的，所以我們將兩個木板中最短的那一個做改變，才有可能得到一個更大的容器。

這個解釋模模糊糊說得通，但似乎并不是那么嚴(yán)格。關(guān)鍵在于，這個解釋沒有說明：這個算法為什么沒有漏掉一個可能的更大面積的容器？

Leetcode 的討論區(qū)有很多關(guān)于這個算法的正確性的討論，但我覺得大多數(shù)敘述的語言過于理論化了。也有同學(xué)在我的課程問答區(qū)問過我這個問題，所以，我寫了這篇文章，嘗試闡述一下這個問題。

我們來看初始的時候，left 指向 a[0]，right 指向 a[n-1]。我們假設(shè) a[0] 是小于 a[n-1] 的，即 a[0] < a[n-1]。那么下一步，根據(jù)我們的算法，就是 left ++，即 left 下一步指向了 a[1]。

這意味著什么？這就意味著，使用 a[0] 和 a[n-2]；使用 a[0] 和 a[n-3]；使用 a[0] 和 a[n-4]；.... ；使用 a[0] 和 a[1]，這些木板的組合，我們都直接跳過去了，不去計算了。

換句話說，因為我們直接 left ++ 了，所以所有的以 a[0] 為左邊木板的其他組合，都不看了。

為什么可以這樣？

還記得我們的假設(shè)嗎？a[0] 是小于 a[n-1] 的。所以，此時，整個容器的高度，是由 a[0] 決定的。因為，如果右邊板的高度大于 a[0]，我們?nèi)《贪?，容器的高度還是 a[0]；如果右邊的高度小于 a[0]，那么容器的高度比 a[0] 還要小。

而對于其他的以 a[0] 為左邊木板的組合：a[0] 和 a[1]，a[0] 和 a[2]，a[0] 和 a[3]，...，a[0] 和 a[n-2]，底的長度都比 a[0] 和 a[n-1] 更小。而高度又不會超過 a[0]，所以，面積一定是更小的，我們就可以直接排除掉！

那么這個過程，我們一下子排除了多少組組合呢？答案是，左邊是 a[0]，右邊是 a[1] ... a[n-2]，一共 n-2 組組合，直接被我們?nèi)拥袅恕?/p>

當(dāng)然，如果我們假設(shè) a[0] > a[n-1]，這個邏輯同樣成立，只不過我們?nèi)拥舻慕M合，右邊固定為 a[n-1]，左邊是 a[1] 到 a[n-2]，還是 n-2 個組合。

現(xiàn)在，假設(shè)我們的 left 指向 1 了，right 還是 n-1。再假設(shè)，這次是 a[1] > a[n-1] 了。那么，按照我們的算法，就應(yīng)該是 right-- 了。

這次，有了上面的分析，相信大家就都理解了，我們不需要比較 a[2] 和 a[n-1]；a[3] 和 a[n-1]；a[4] 和 a[n-1]；...；a[n-3] 和 a[n-1]，a[n-2] 和 a[n-1]，這些組合了。

為什么？因為此時，a[1] 和 a[n-1] 這個組合中，容器的高度是由右邊的板 a[n-1] 決定的。那么剩下的以 a[n-1] 為右側(cè)板的所有容器，高度不可能大于 a[n-1] 了，而底卻在縮小，所以，這些組合都可以直接扔掉，不計算了。

那么這次，我們?nèi)拥袅硕嗌賯€組合？答案是右邊固定為 a[n - 1]，左邊是 a[2], a[3],...,a[n-2]，一共 n-3 個組合！

相信大家可以看出規(guī)律來了。我們每次左指針或者右指針移動一次，其實都是扔掉了若干組合，不再需要比較了。

第一次移動，扔掉了 n-2 個組合；第二次移動，扔掉了 n-3 個組合；第三次移動，將扔掉 n-4 個組合，依次類推，直到最后一次移動，扔掉 1 個組合。

那么，我們在這個過程中，總共扔掉了多少組合？就是 1, 2, 3, ... , n-4, n-3, n-2 的和。大家可以看出來，這又是一個等差數(shù)列。首項是 1，末項是 n-2，一共 n-2 項。

帶入等差數(shù)列求和公式，我們一共扔掉了 (n-1)*(n-2)/2 這么多個組合，不用去考慮。

現(xiàn)在，大家就可以計算一下了?；貞浺幌律厦娴臄⑹觯?/p>

我們一共扔掉了 (n-1)*(n-2)/2 這么多組合，只計算了 n-1 這么多組合。

把他們加起來，是多少？

答案是 n * (n - 1) / 2！

大家回憶一下，這個數(shù)字正好就是 n 塊木板，抽出兩塊，組成容器的所有可能方案！

C(n, 2) = n * (n - 1) / 2！

那么這也就證明了，我們的雙指針?biāo)惴?，比較了 n-1 組木板，扔掉了 (n-1)*(n-2)/2 組木板，合在一起，已經(jīng)完整地考慮了所有 n * (n - 1) / 2 組木板的組合了。

我們這個過程，不會漏掉任何一個組合，最終找到的解，一定是最優(yōu)解！

怎么樣？是不是覺得這個證明理解起來并不難？

值得一提的是，雖然我們說這個問題是雙指針的問題，但其實，在算法設(shè)計上，我們使用了貪心的思想。即每次把最短木板對應(yīng)的所有其余組合都扔掉了。

而對于貪心算法來說，最大的特點就是：通常代碼都會比較簡單，但要想證明貪心的正確性，會比較費勁。這個問題就是一個很好的例子。

實際上，在 Leetcode 上，還有很多貪心的問題，擁有這樣的特點。以后有機會，可以再向大家介紹。