Leetcode上第11號(hào)問題：盛最多水的容器

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

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

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

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

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

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

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

res=0; for(i=0;i

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

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

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

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

以此類推...

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

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

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

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

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

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

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

算法偽碼大概是這樣的：

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

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

這個(gè)算法的復(fù)雜度是 O(n) 的。因?yàn)檎麄€(gè)算法中，每一個(gè)木板都或者被 left 指針指過(guò)一次，或者被 right 指針指過(guò)一次，直到 left 和 right 匯合。

對(duì)應(yīng)的，res 一共被計(jì)算了 n-1 次。因?yàn)閮蓚€(gè)木板才能形成一個(gè)容器。使用這種方式，n 個(gè)木板，一共組成了 n-1 個(gè)容器。

這個(gè)算法看起來(lái)非常簡(jiǎn)單，但是，一個(gè)很致命的問題是：這個(gè)算法為什么是正確的？

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

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

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

我們來(lái)看初始的時(shí)候，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]，這些木板的組合，我們都直接跳過(guò)去了，不去計(jì)算了。

換句話說(shuō)，因?yàn)槲覀冎苯?left ++ 了，所以所有的以 a[0] 為左邊木板的其他組合，都不看了。

為什么可以這樣？

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

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

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

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

現(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]，這些組合了。

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

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

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

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

那么，我們?cè)谶@個(gè)過(guò)程中，總共扔掉了多少組合？就是 1, 2, 3, ... , n-4, n-3, n-2 的和。大家可以看出來(lái)，這又是一個(gè)等差數(shù)列。首項(xiàng)是 1，末項(xiàng)是 n-2，一共 n-2 項(xiàng)。

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

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

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

把他們加起來(lái)，是多少？

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

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

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

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

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

怎么樣？是不是覺得這個(gè)證明理解起來(lái)并不難？

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

而對(duì)于貪心算法來(lái)說(shuō)，最大的特點(diǎn)就是：通常代碼都會(huì)比較簡(jiǎn)單，但要想證明貪心的正確性，會(huì)比較費(fèi)勁。這個(gè)問題就是一個(gè)很好的例子。

實(shí)際上，在 Leetcode 上，還有很多貪心的問題，擁有這樣的特點(diǎn)。以后有機(jī)會(huì)，可以再向大家介紹。