接雨水問題的三種解法:暴力/備忘錄/雙指針

42. 接雨水（困難）

接雨水這道題目挺有意思，在面試題中出現(xiàn)頻率還挺高的，本文就來(lái)步步優(yōu)化，講解一下這道題。

先看一下題目：

就是用一個(gè)數(shù)組表示一個(gè)條形圖，問你這個(gè)條形圖最多能接多少水。

inttrap(int[]height);

下面就來(lái)由淺入深介紹暴力解法 -> 備忘錄解法 -> 雙指針解法，在 O(N) 時(shí)間 O(1) 空間內(nèi)解決這個(gè)問題。

一、核心思路

所以對(duì)于這種問題，我們不要想整體，而應(yīng)該去想局部；就像之前的文章寫的動(dòng)態(tài)規(guī)劃問題處理字符串問題，不要考慮如何處理整個(gè)字符串，而是去思考應(yīng)該如何處理每一個(gè)字符。

這么一想，可以發(fā)現(xiàn)這道題的思路其實(shí)很簡(jiǎn)單。具體來(lái)說(shuō)，僅僅對(duì)于位置i，能裝下多少水呢？

能裝 2 格水，因?yàn)?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">height[i]的高度為 0，而這里最多能盛 2 格水，2-0=2。

為什么位置i最多能盛 2 格水呢？因?yàn)椋恢?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">i能達(dá)到的水柱高度和其左邊的最高柱子、右邊的最高柱子有關(guān)，我們分別稱這兩個(gè)柱子高度為l_max和r_max；位置 i 最大的水柱高度就是min(l_max, r_max)。

更進(jìn)一步，對(duì)于位置i，能夠裝的水為：

water[i]=min(
#左邊最高的柱子
max(height[0..i]),
#右邊最高的柱子
max(height[i..end])
)-height[i]

這就是本問題的核心思路，我們可以簡(jiǎn)單寫一個(gè)暴力算法：

inttrap(int[]height){
intn=height.length;
intres=0;
for(inti=1;i1;i++){
intl_max=0,r_max=0;
//找右邊最高的柱子
for(intj=i;j//找左邊最高的柱子
for(intj=i;j>=0;j--)
l_max=Math.max(l_max,height[j]);
//如果自己就是最高的話，
//l_max==r_max==height[i]
res+=Math.min(l_max,r_max)-height[i];
}
returnres;
}

有之前的思路，這個(gè)解法應(yīng)該是很直接粗暴的，時(shí)間復(fù)雜度 O(N^2)，空間復(fù)雜度 O(1)。但是很明顯這種計(jì)算r_max和l_max的方式非常笨拙，一般的優(yōu)化方法就是備忘錄。

二、備忘錄優(yōu)化

之前的暴力解法，不是在每個(gè)位置i都要計(jì)算r_max和l_max嗎？我們直接把結(jié)果都提前計(jì)算出來(lái)，別傻不拉幾的每次都遍歷，這時(shí)間復(fù)雜度不就降下來(lái)了嘛。

我們開兩個(gè)數(shù)組r_max和l_max充當(dāng)備忘錄，l_max[i]表示位置i左邊最高的柱子高度，r_max[i]表示位置i右邊最高的柱子高度。預(yù)先把這兩個(gè)數(shù)組計(jì)算好，避免重復(fù)計(jì)算：

inttrap(int[]height){
if(height.length==0){
return0;
}
intn=height.length;
intres=0;
//數(shù)組充當(dāng)備忘錄
int[]l_max=newint[n];
int[]r_max=newint[n];
//初始化basecase
l_max[0]=height[0];
r_max[n-1]=height[n-1];
//從左向右計(jì)算l_max
for(inti=1;i1]);
//從右向左計(jì)算r_max
for(inti=n-2;i>=0;i--)
r_max[i]=Math.max(height[i],r_max[i+1]);
//計(jì)算答案
for(inti=1;i1;i++)
res+=Math.min(l_max[i],r_max[i])-height[i];
returnres;
}

這個(gè)優(yōu)化其實(shí)和暴力解法思路差不多，就是避免了重復(fù)計(jì)算，把時(shí)間復(fù)雜度降低為 O(N)，已經(jīng)是最優(yōu)了，但是空間復(fù)雜度是 O(N)。下面來(lái)看一個(gè)精妙一些的解法，能夠把空間復(fù)雜度降低到 O(1)。

三、雙指針解法

這種解法的思路是完全相同的，但在實(shí)現(xiàn)手法上非常巧妙，我們這次也不要用備忘錄提前計(jì)算了，而是用雙指針邊走邊算，節(jié)省下空間復(fù)雜度。

首先，看一部分代碼：

inttrap(int[]height){
intleft=0,right=height.length-1;
intl_max=0,r_max=0;

while(left//此時(shí) l_max 和 r_max 分別表示什么？
left++;right--;
}
}

對(duì)于這部分代碼，請(qǐng)問l_max和r_max分別表示什么意義呢？

很容易理解，l_max是height[0..left]中最高柱子的高度，r_max是height[right..end]的最高柱子的高度。

明白了這一點(diǎn)，直接看解法：

inttrap(int[]height){
intleft=0,right=height.length-1;
intl_max=0,r_max=0;

intres=0;
while(left//res+=min(l_max,r_max)-height[i]
if(l_maxelse{
res+=r_max-height[right];
right--;
}
}
returnres;
}

你看，其中的核心思想和之前一模一樣，換湯不換藥。但是細(xì)心的讀者可能會(huì)發(fā)現(xiàn)次解法還是有點(diǎn)細(xì)節(jié)差異：

之前的備忘錄解法，l_max[i]和r_max[i]分別代表height[0..i]和height[i..end]的最高柱子高度。

res+=Math.min(l_max[i],r_max[i])-height[i];

但是雙指針解法中，l_max和r_max代表的是height[0..left]和height[right..end]的最高柱子高度。比如這段代碼：

if(l_max

此時(shí)的l_max是left指針左邊的最高柱子，但是r_max并不一定是left指針右邊最高的柱子，這真的可以得到正確答案嗎？

其實(shí)這個(gè)問題要這么思考，我們只在乎min(l_max, r_max)。對(duì)于上圖的情況，我們已經(jīng)知道l_max < r_max了，至于這個(gè)r_max是不是右邊最大的，不重要。重要的是height[i]能夠裝的水只和較低的l_max之差有關(guān)：

這樣，接雨水問題就解決了。

擴(kuò)展延伸

下面我們看一道和接雨水問題非常類似的題目，力扣第 11 題「盛最多水的容器」：

函數(shù)簽名如下：

intmaxArea(int[]height);

這題和接雨水問題很類似，可以完全套用前文的思路，而且還更簡(jiǎn)單。兩道題的區(qū)別在于：

接雨水問題給出的類似一幅直方圖，每個(gè)橫坐標(biāo)都有寬度，而本題給出的每個(gè)橫坐標(biāo)是一條豎線，沒有寬度。

我們前文討論了半天l_max和r_max，實(shí)際上都是為了計(jì)算height[i]能夠裝多少水；而本題中height[i]沒有了寬度，那自然就好辦多了。

舉個(gè)例子，如果在接雨水問題中，你知道了height[left]和height[right]的高度，你能算出left和right之間能夠盛下多少水嗎？

不能，因?yàn)槟悴恢?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">left和right之間每個(gè)柱子具體能盛多少水，你得通過(guò)每個(gè)柱子的l_max和r_max來(lái)計(jì)算才行。

反過(guò)來(lái)，就本題而言，你知道了height[left]和height[right]的高度，能算出left和right之間能夠盛下多少水嗎？

可以，因?yàn)楸绢}中豎線沒有寬度，所以left和right之間能夠盛的水就是：

min(height[left],height[right])*(right-left)

類似接雨水問題，高度是由height[left]和height[right]較小的值決定的。

解決這道題的思路依然是雙指針技巧：

用left和right兩個(gè)指針從兩端向中心收縮，一邊收縮一邊計(jì)算[left, right]之間的矩形面積，取最大的面積值即是答案。

先直接看解法代碼吧：

intmaxArea(int[]height){
intleft=0,right=height.length-1;
intres=0;
while(left//[left,right]之間的矩形面積
intcur_area=Math.min(height[left],height[right])*(right-left);
res=Math.max(res,cur_area);
//雙指針技巧，移動(dòng)較低的一邊
if(height[left]else{
right--;
}
}
returnres;
}

代碼和接雨水問題大致相同，不過(guò)肯定有讀者會(huì)問，下面這段 if 語(yǔ)句為什么要移動(dòng)較低的一邊：

//雙指針技巧，移動(dòng)較低的一邊
if(height[left]else{
right--;
}

其實(shí)也好理解，因?yàn)榫匦蔚母叨仁怯?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">min(height[left], height[right])即較低的一邊決定的：

你如果移動(dòng)較低的那一邊，那條邊可能會(huì)變高，使得矩形的高度變大，進(jìn)而就「有可能」使得矩形的面積變大；相反，如果你去移動(dòng)較高的那一邊，矩形的高度是無(wú)論如何都不會(huì)變大的，所以不可能使矩形的面積變得更大。

至此，這道題也解決了。