手把手搞懂接雨水問題的多種解法
讀完本文，可以去力扣解決如下題目：
42.接雨水（Hard）
接雨水這道題目挺有意思，在面試題中出現(xiàn)頻率還挺高的，本文就來步步優(yōu)化，講解一下這道題：
就是用一個數(shù)組表示一個條形圖，問你這個條形圖最多能接多少水，函數(shù)簽名如下：
int?trap(int[]?height);
下面就來由淺入深介紹暴力解法 -> 備忘錄解法 -> 雙指針解法，在 O(N) 時間 O(1) 空間內(nèi)解決這個問題。
一、暴力解法
對于這種問題，我們不要想整體，而應(yīng)該去想局部；就像之前的文章寫的動態(tài)規(guī)劃問題處理字符串問題，不要考慮如何處理整個字符串，而是去思考應(yīng)該如何處理每一個字符。
這么一想，可以發(fā)現(xiàn)這道題的思路其實很簡單。具體來說，僅僅對于位置i，能裝下多少水呢？
能裝 2 格水，因為height[i]的高度為 0，而這里最多能盛 2 格水，2-0=2。
為什么位置i最多能盛 2 格水呢？因為，位置i能達(dá)到的水柱高度和其左邊的最高柱子、右邊的最高柱子有關(guān)，我們分別稱這兩個柱子高度為l_max和r_max；位置 i 最大的水柱高度就是min(l_max, r_max)。
更進(jìn)一步，對于位置i，能夠裝的水為：
water[i]?=?min(
???????????????#?左邊最高的柱子
???????????????max(height[0..i]),??
???????????????#?右邊最高的柱子
???????????????max(height[i..end])?
????????????)?-?height[i]
這就是本問題的核心思路，我們可以簡單寫一個暴力算法：int?trap(vector<int>&?height)?{
????int?n?=?height.size();
????int?res?=?0;
????for?(int?i?=?1;?i?1;?i++)?{
????????int?l_max?=?0,?r_max?=?0;
????????//?找右邊最高的柱子
????????for?(int?j?=?i;?j?????????????r_max?=?max(r_max,?height[j]);
????????//?找左邊最高的柱子
????????for?(int?j?=?i;?j?>=?0;?j--)
????????????l_max?=?max(l_max,?height[j]);
????????//?如果自己就是最高的話，
????????//?l_max?==?r_max?==?height[i]
????????res?+=?min(l_max,?r_max)?-?height[i];
????}
????return?res;
}
有之前的思路，這個解法應(yīng)該是很直接粗暴的，時間復(fù)雜度 O(N^2)，空間復(fù)雜度 O(1)。但是很明顯這種計算r_max和l_max的方式非常笨拙，一般的優(yōu)化方法就是備忘錄。
二、備忘錄優(yōu)化
之前的暴力解法，不是在每個位置i都要計算r_max和l_max嗎？我們直接把結(jié)果都提前計算出來，別傻不拉幾的每次都遍歷，這時間復(fù)雜度不就降下來了嘛。
我們開兩個數(shù)組r_max和l_max充當(dāng)備忘錄，l_max[i]表示位置i左邊最高的柱子高度，r_max[i]表示位置i右邊最高的柱子高度。預(yù)先把這兩個數(shù)組計算好，避免重復(fù)計算：
int?trap(vector<int>&?height)?{
????if?(height.empty())?return?0;
????int?n?=?height.size();
????int?res?=?0;
????//?數(shù)組充當(dāng)備忘錄
????vector<int>?l_max(n),?r_max(n);
????//?初始化?base?case
????l_max[0]?=?height[0];
????r_max[n?-?1]?=?height[n?-?1];
????//?從左向右計算?l_max
????for?(int?i?=?1;?i?????????l_max[i]?=?max(height[i],?l_max[i?-?1]);
????//?從右向左計算?r_max
????for?(int?i?=?n?-?2;?i?>=?0;?i--)?
????????r_max[i]?=?max(height[i],?r_max[i?+?1]);
????//?計算答案
????for?(int?i?=?1;?i?1;?i++)?
????????res?+=?min(l_max[i],?r_max[i])?-?height[i];
????return?res;
}
這個優(yōu)化其實和暴力解法思路差不多，就是避免了重復(fù)計算，把時間復(fù)雜度降低為 O(N)，已經(jīng)是最優(yōu)了，但是空間復(fù)雜度是 O(N)。下面來看一個精妙一些的解法，能夠把空間復(fù)雜度降低到 O(1)。
三、雙指針解法
這種解法的思路是完全相同的，但在實現(xiàn)手法上非常巧妙，我們這次也不要用備忘錄提前計算了，而是用雙指針邊走邊算，節(jié)省下空間復(fù)雜度。
首先，看一部分代碼：
int?trap(vector<int>&?height)?{
????int?n?=?height.size();
????int?left?=?0,?right?=?n?-?1;
????int?l_max?=?height[0];
????int?r_max?=?height[n?-?1];
????while?(left?<=?right)?{
????????l_max?=?max(l_max,?height[left]);
????????r_max?=?max(r_max,?height[right]);
????????left++;?right--;
????}
}
對于這部分代碼，請問l_max和r_max分別表示什么意義呢？
很容易理解，l_max是height[0..left]中最高柱子的高度，r_max是height[right..n-1]的最高柱子的高度。
明白了這一點(diǎn)，直接看解法：
int?trap(vector<int>&?height)?{
????if?(height.empty())?return?0;
????int?n?=?height.size();
????int?left?=?0,?right?=?n?-?1;
????int?res?=?0;
????int?l_max?=?height[0];
????int?r_max?=?height[n?-?1];
????while?(left?<=?right)?{
????????l_max?=?max(l_max,?height[left]);
????????r_max?=?max(r_max,?height[right]);
????????//?res?+=?min(l_max,?r_max)?-?height[i]
????????if?(l_max?????????????res?+=?l_max?-?height[left];
????????????left++;?
????????}?else?{
????????????res?+=?r_max?-?height[right];
????????????right--;
????????}
????}
????return?res;
}
你看，其中的核心思想和之前一模一樣，換湯不換藥。但是細(xì)心的讀者可能會發(fā)現(xiàn)次解法還是有點(diǎn)細(xì)節(jié)差異：
之前的備忘錄解法，l_max[i]和r_max[i]分別代表height[0..i]和height[i..n-1]的最高柱子高度。
res?+=?min(l_max[i],?r_max[i])?-?height[i];
但是雙指針解法中，l_max和r_max代表的是height[0..left]和height[right..n-1]的最高柱子高度。比如這段代碼：
if?(l_max?????res?+=?l_max?-?height[left];
????left++;?
}?
此時的l_max是left指針左邊的最高柱子，但是r_max并不一定是left指針右邊最高的柱子，這真的可以得到正確答案嗎？
其實這個問題要這么思考，我們只在乎min(l_max, r_max)。對于上圖的情況，我們已經(jīng)知道l_max < r_max了，至于這個r_max是不是右邊最大的，不重要。重要的是height[i]能夠裝的水只和較低的l_max之差有關(guān)：
這樣，接雨水問題就解決了，學(xué)會了嗎？三連安排！