本期精選題解由我們的用戶“windliang”傾情撰寫，一起來看看吧！

力扣 42.接雨水

題目描述

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。

上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。 感謝 Marcos 貢獻此圖。

示例:

解決方案

思路

黑色的看成牆，藍色的看成水，寬度一樣，給定一個數組，每個數代表從左到右牆的高度，求出能裝多少單位的水。也就是圖中藍色正方形的個數。

解法一：按列求

求每一列的水，我們只需要關注當前列，以及左邊最高的牆，右邊最高的牆就夠了。

裝水的多少，當然根據木桶效應，我們只需要看左邊最高的牆和右邊最高的牆中較矮的一個就夠了。

所以，根據較矮的那個牆和當前列的牆的高度可以分為三種情況。

• 較矮的牆的高度大於當前列的牆的高度

把正在求的列左邊最高的牆和右邊最高的牆確定後，然後為了方便理解，我們把無關的牆去掉。

這樣就很清楚了，現在想象一下，往兩邊最高的牆之間注水。正在求的列會有多少水？

很明顯，較矮的一邊，也就是左邊的牆的高度，減去當前列的高度就可以了，也就是 2 - 1 = 1，可以存一個單位的水。

• 較矮的牆的高度小於當前列的牆的高度

同樣的，我們把其他無關的列去掉。

想象下，往兩邊最高的牆之間注水。正在求的列會有多少水？

正在求的列不會有水，因為它大於了兩邊較矮的牆。

• 較矮的牆的高度等於當前列的牆的高度。

和上一種情況是一樣的，不會有水。

明白了這三種情況，程序就很好寫了，遍歷每一列，然後分別求出這一列兩邊最高的牆。找出較矮的一端，和當前列的高度比較，結果就是上邊的三種情況。

時間複雜度：O(n^2），遍歷每一列需要 n，找出左邊最高和右邊最高的牆加起來剛好又是一個 n，所以是 n^2。

空間複雜度：O(1）。

解法二: 動態規劃

我們注意到，解法二中。對於每一列，我們求它左邊最高的牆和右邊最高的牆，都是重新遍歷一遍所有高度，這裡我們可以優化一下。

首先用兩個數組，max_left [i]代表第 i 列左邊最高的牆的高度，max_right[i] 代表第 i 列右邊最高的牆的高度。（一定要注意下，第 i 列左（右）邊最高的牆，是不包括自身的，和力扣上邊的講的有些不同）

對於 max_left我們其實可以這樣求。

max_left [i] = Max(max_left [i-1],height[i-1])。它前邊的牆的左邊的最高高度和它前邊的牆的高度選一個較大的，就是當前列左邊最高的牆了。

對於 max_right我們可以這樣求。

max_right[i] = Max(max_right[i+1],height[i+1]) 。它後邊的牆的右邊的最高高度和它後邊的牆的高度選一個較大的，就是當前列右邊最高的牆了。

這樣，我們再利用解法二的算法，就不用在 for 循環裡每次重新遍歷一次求 max_left 和 max_right 了。

時間複雜度：O(n)。

空間複雜度：O(n)，用來保存每一列左邊最高的牆和右邊最高的牆。

解法三：雙指針

動態規劃中，我們常常可以對空間複雜度進行進一步的優化。

例如這道題中，可以看到，max_left [ i ] 和 max_right [ i ] 數組中的元素我們其實只用一次，然後就再也不會用到了。所以我們可以不用數組，只用一個元素就行了。我們先改造下 max_left。

我們成功將 max_left 數組去掉了。但是會發現我們不能同時把 max_right 的數組去掉，因為最後的 for 循環是從左到右遍歷的，而 max_right 的更新是從右向左的。

所以這裡要用到兩個指針，left 和 right，從兩個方向去遍歷。

那麼什麼時候從左到右，什麼時候從右到左呢？根據下邊的代碼的更新規則，我們可以知道

height [ left - 1] 是可能成為 max_left 的變量，同理，height [ right + 1 ] 是可能成為 right_max 的變量。

只要保證 height [ left - 1 ] < height [ right + 1 ] ，那麼 max_left 就一定小於 max_right。

因為 max_left 是由 height [ left - 1] 更新過來的，而 height [ left - 1 ] 是小於 height [ right + 1] 的，而 height [ right + 1 ] 會更新max_right，所以間接的得出 max_left 一定小於 max_right。

反之，我們就從右到左更。

時間複雜度：O(n)。

空間複雜度：O(1)。

解法四：棧

說到棧，我們肯定會想到括號匹配了。我們仔細觀察藍色的部分，可以和括號匹配類比下。每次匹配出一對括號（找到對應的一堵牆），就計算這兩堵牆中的水。

我們用棧保存每堵牆。

當遍歷牆的高度的時候，如果當前高度小於棧頂的牆高度，說明這裡會有積水，我們將牆的高度的下標入棧。

如果當前高度大於棧頂的牆的高度，說明之前的積水到這裡停下，我們可以計算下有多少積水了。計算完，就把當前的牆繼續入棧，作為新的積水的牆。

總體的原則就是，

1. 當前高度小於等於棧頂高度，入棧，指針後移。
2. 當前高度大於棧頂高度，出棧，計算出當前牆和棧頂的牆之間水的多少，然後計算當前的高度和新棧的高度的關係，重複第 2 步。直到當前牆的高度不大於棧頂高度或者棧空，然後把當前牆入棧，指針後移。

我們看具體的例子。

• 首先將 height [ 0 ] 入棧。然後 current 指向的高度大於棧頂高度，所以把棧頂 height [ 0 ] 出棧，然後棧空了，再把 height [ 1 ] 入棧。current 後移。

• 然後 current 指向的高度小於棧頂高度，height [ 2 ] 入棧，current 後移。

• 然後 current 指向的高度大於棧頂高度，棧頂 height [ 2 ] 出棧。計算 height [ 3 ] 和新的棧頂之間的水。計算完之後繼續判斷 current 和新的棧頂的關係。

• current 指向的高度大於棧頂高度，棧頂 height [ 1 ] 出棧，棧空。所以把 height [ 3 ] 入棧。currtent 後移。

• 然後 current 指向的高度小於棧頂 height [ 3 ] 的高度，height [ 4 ] 入棧。current 後移。

• 然後 current 指向的高度小於棧頂 height [ 4 ] 的高度，height [ 5 ] 入棧。current 後移。

• 然後 current 指向的高度大於棧頂 height [ 5 ] 的高度，將棧頂 height [ 5 ] 出棧，然後計算 current 指向的牆和新棧頂 height [ 4 ] 之間的水。計算完之後繼續判斷 current 的指向和新棧頂的關係。此時 height [ 6 ] 不大於棧頂height [ 4 ] ，所以將 height [ 6 ] 入棧。current 後移。

• 然後 current 指向的高度大於棧頂高度，將棧頂 height [ 6 ] 出棧。計算和新的棧頂 height [ 4 ] 組成兩個邊界中的水。然後判斷 current 和新的棧頂 height [ 4 ] 的關係，依舊是大於，所以把 height [ 4 ] 出棧。計算 current 和 新的棧頂 height [ 3 ] 之間的水。然後判斷 current 和新的棧頂 height [ 3 ] 的關係，依舊是大於，所以把 height [ 3 ] 出棧，棧空。將 current 指向的 height [ 7 ] 入棧。current 後移。

其實不停的出棧，可以看做是在找與 7 匹配的牆，也就是 3 。

而對於計算 current 指向牆和新的棧頂之間的水，根據圖的關係，我們可以直接把這兩個牆當做之前解法三的 max_left 和 max_right，然後之前彈出的棧頂當做每次遍歷的 height [ i ]。水量就是 Min ( max _ left ，max _ right ) - height [ i ]，只不過這裡需要乘上兩個牆之間的距離。可以看下代碼繼續理解下。

時間複雜度：雖然 while 循環裡套了一個 while 循環，但是考慮到每個元素最多訪問兩次，入棧一次和出棧一次，所以時間複雜度是 O(n)。

空間複雜度：O(n)。棧的空間。

總結

解法一到解法二，利用動態規劃，空間換時間，解法二到解法三，優化動態規劃的空間，這一系列下來，讓人心曠神怡。