單調棧、構造法、two pointers，這道Hard題的解法這麼多？

今天是LeetCode專題的第23篇文章。

今天來看一道很有意思的題，它的難度是Hard，並且有許多種解法。

首先我們來看題面，說是我們有若干個水壩，水壩的寬都是1，但是水壩的高度參差不齊。某一天我們向水壩圍起來的部分灌水，一直到灌滿為止，請問水壩中存儲了多少單位的水？我們可以參考一下下圖：

上圖當中黑色的部分是水壩，藍色的部分是存儲的水。所有的水壩的寬度是1，長度是整數，不考慮損耗。

我們的輸入是一個數組，表示若干個水壩的高度，要求的輸出是一個整數，表示這些水壩圍起來的面積。比如上圖的樣例為：

<code>Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6/<code>

暴力

這題剛拿到手比較棘手，因為我們只知道水壩的高度，並不知道水壩圍成了多少個區域，也不知道這些區域當中的形狀是怎樣的。

還是老規矩，我們先來思考暴力解法。在這題當中暴力解法可能不是非常明顯，我們需要仔細分析一下上圖當中的數據。

從上圖樣例當中我們可以看到，這些水壩由於高低不齊，會導致整個水壩中的水並不是一個整體，而是會被分成好幾個部分。也就是說我們沒辦法直接求到結果，而需要對這些部分分別求水的體積，最後相加。

但是我們並不知道水壩中的水會被分成幾個部分，所以直接求是不行的，那麼有沒有什麼辦法可以確定我們找到了一個完整的部分呢？

我們先把這個問題簡化一下，在什麼情況下水壩有存儲水的能力呢？

如果水壩的高度遞增行嗎？那如果遞減呢？

我們在紙上畫一畫很容易就想明白，遞增和遞減都不行，只有先遞減再遞增可以，也就是下圖所示這樣。

我們看下上圖，水壩的高度先遞減再遞增，這樣兩邊比較高的水壩就可以攔住一定體積的水。我們再思考一下，如果上圖只是所有水壩的一部分，我們可以保證這個部分是完整的嗎？顯然應該不是，原因也很簡單，因為水壩的右側可能還會出現更高的水壩，如果出現了，那麼整個部分的水平面還會提升，也就是說能存下更多的水，也就是下圖的情況：

我們對照一下這兩張圖就可以想明白，當我們從左往右遍歷的時候，只有遇到比最左側的水壩更高的水壩的時候，這個部分才完整。想明白這點就容易了，我們從左往右遍歷，維護一個局部最高值，當發現一個比局部最高值相等或更高的值的時候，就說明可以存儲一部分的水，並且這部分水是完整的，我們來計算一下圍成的水的面積。水的面積也很容易算，我們算出水平面的高度，然後減去水面下水壩的高度即可。

所以我們首先找到這樣一個一個完整的水域，計算出每個水域的面積，最後將水域的總面積相加得到最終的結果。

思路是正確的，但是實現的時候會發現有點問題，什麼問題呢？我們還拿上面的例子距離，你會發現當我們到達最高點了之後，後面的完整水域切分不出來了，因為沒有比最高點更高的了。

上圖當中箭頭標的位置是最高點，它的右側再沒有比它高的位置。我們是通過右側出現大於或者等於它高度的水壩出現作為判斷完整水域的條件，如果沒有出現，我們就沒辦法判斷究竟完整的水域能夠延伸到哪裡了。

這個問題比較棘手，我能想到最好的辦法是將後面的部分翻轉過來重複執行一次同樣的操作。這是實現最簡單代碼最小的方法了。

我們試著寫下代碼：

當然也可以不用翻轉，而是換成從右往左遍歷，都是可以的。

two pointers

不知道大家理解了暴力解法之後，有沒有一個想法，既然我們總可以找到一個最高的水壩（如果出現多個，則認為最右側的那個最高），那麼我們是不是可以根據這個最高的水壩的位置，將整個水庫分成左右兩個部分，然後從左右兩個邊界朝著中間收縮呢？

也就是說用和剛才一樣的方法劃分完整的水域，只不過我們用兩個指針從兩邊一起遍歷，一個指針從左往右，另一個指針從右往左。還是一樣，當碰到大於等於目前最大值的時候認為是一個完整的水域，計算面積。

似乎這種方法和上面的一樣，但其實不然，仔細分析可以發現一個優化的點。

在之前的方法當中，我們並不確定我們從左往右一定可以找到比目前最大值更大的值。很有可能之前找到的最大值就是全局最大的，後面不會有更大的值出現。所以我們必須要等更大的值出現之後才能計算水域的面積。

而兩個指針的方法當中，我們每次移動其中較小的那個，這樣我們可以保證兩個指針相遇的位置就是全局最大值。既然我們可以保證兩個指針會相遇在全局最大值，那麼移動指針的時候就可以保證後面一定還會有更高的位置出現

我們來看個例子：

在上圖的例子當中，r指針的高度是3，大於目前的l，我們需要移動指針l，目前左邊遇見的最大值是2。由於l和r沒有相遇，所以我們可以保證l的右側一定還有大於left_max的高度出現，否則該移動的就是r了。所以我們可以保證，

在這個算法當中，我們控制兩個指針移動，當兩個指針相遇的時候則結束。可以想明白，我們一共移動了n次，所以這是一個 O(n) 的算法，我們來看下代碼裡的細節：

和上面的代碼相比，這段代碼要簡明很多，看起來也更順眼。雖然代碼簡單，但是能把其中的門道想明白並不容易，如果有覺得迷糊的同學可以結合上面的圖片再思考思考，舉例子作圖是思考算法各種情況的王道，這個辦法大家一定要掌握。

構造法

如果真的理解了上面的解法會發現上面的解法本質上是將水域進行縱向切分，然後每一塊單獨累加來計算總面積的，也就是這樣：

既然本質都是切分，那麼我們能不能不搞那麼多花哨的操作直接進行切分呢？當然是可以的，難點只有一個，就是我們需要知道當前的水平面的高度，這個是核心問題。我們之前搞那麼多高度比來比去本質也是為了求水平面的高度。

那麼有沒有什麼辦法可以直接求到水平面的高度呢？其實是有的，方法很簡單也很粗暴。我們分析一下上圖，可以發現，對於未知i來說，它的水平面高度是由兩個水壩決定的。也就是i兩邊最高的水壩。

比如對於上圖的例子來說，i位置的水平面高度是由它左側最高的l和右側最高的r其中較小的那個高度決定的。我們並不關心l和r的下標是多少，我們只關心它的高度。既然如此，我們把所有i左右兩側最高的高度記錄下來不就行了？

我相信如果你是自己想到的這個方法，在你想通的那一刻，你一定會覺得自己實在是太機智了。

道理想明白了，編碼完全沒有難度，我們隨手就來：

這個算法同樣是 O(n) 的複雜度，但是實現起來比上面的還要簡單。雖然我們單純看解法它簡單得難以置信，但是能夠想到這個簡單的解法並不容易，除了需要我們充分理解題意之外，更需要我們有一定的解題技巧和思維靈敏度。

最後，我們來看本篇文章的大菜，也是本題的最後一個經典解法——單調棧

單調棧

在我們介紹具體的算法之前，我們先來看一下單調棧這個數據結構。嚴格說起來它並不是新的數據結構，只是棧的簡單變種。

顧名思義，單調棧即棧的元素都是

舉個例子，比如說目前棧內的數據是[3, 7, 10]遞增排列，棧頂的位置是10。如果我們需要插入16，由於它大於10，所以我們可以直接插入棧頂，棧會變成[3, 7, 10, 16]。如果我們要插入的元素是8，由於它小於10，所以我們會彈出棧頂的10，接著和7比較，發現它大於7，那麼插入，得到[3, 7, 8]。也就是說通過單調棧我們可以保證棧內的元素是有序的，以及棧頂的元素是最大或者最小的。

利用這兩個性質，我們可以解決很多問題。

我們先把單調棧放一邊，先回到問題的分析。之前的解法都是縱向切割的水域面積，我們能不能

紅框的內容表示以C水壩為右側擋板構成的面積。

C隔成的面積分為兩塊，一塊麵積是0，一塊的面積是3。面積是0的很好理解，因為寬度為0，面積是3，是因為橫截出來的面積

這一切的基點是水壩C，對於水壩C來說，B是離它最近並且最小的，A是次小的。所以它和A隔出的水域的高度是水壩A和B的高度差，而不是A和C的，我想這點應該不難理解。

那麼，我們需要一個數據結構維護C之前水壩的高度情況，並且需要這個數據結構裡的元素是遞增的。另外，當我們計算完C作為右側擋板形成的面積之後，由於C的出現擋住了它之前所有比它矮的水壩，所以我們需要移除數據結構當中小於C的所有內容。

也就是說我們需要數據結構有序，並且需要拋棄小於當前元素的數據。那麼顯然用單調棧就非常合適。我們在讀入C的高度的時候，先彈出B的下標，我們計算它和C之間的水域面積，再彈出A，我們同樣計算面積，一直到棧空或者棧頂的元素大於C即可，這時候我們插入C。

對於所有的位置，我們都可以重複以上的操作，我們只需要將隔成的面積累加起來即可。我們可以看下代碼，獲取更多細節，雖然這個算法看起來麻煩，但是落在代碼上並不複雜：

光看代碼可能會覺得有一點繞，我們需要結合一下上面的圖，仔細推導一下過程。由於單調棧並沒有涉及元素的排序，並且所有的元素最多隻會進棧和出棧一次，所以這也是一個 O(n) 的算法。但是相比之下，它的常數要比上面介紹的幾種要大一些。

今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。

閱讀更多 承志的算法課堂 的文章

關鍵字: 水域 單調 可以