接雨水

今天給大家?guī)淼氖且坏捞貏e特別特別經(jīng)典的題目接雨水問題，這個(gè)問題是很多算法書上面舉例過的題目。雖然是難度題，但是相對(duì)來說還是比較容易理解的，代碼長度也適中，說了這么多，就一個(gè)意思，大家記得打卡這個(gè)題目啊，真的是很nice的一道題，下面我們來看一下題目描述。

給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

輸入：height =?[0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6

示例 2：

輸入：height =?[4,2,0,3,2,5]
輸出：9

示例3：

輸入：[4,3,2,0,1,1,5]
輸出：13

說明：上面是由數(shù)組 [4,3,2,0,1,1,5]表示的高度圖，在這種情況下，可以接 13個(gè)單位的雨水（見下圖）。

題目解析：

看了上面的示例剛開始刷題的同學(xué)可能有些懵逼，那我們結(jié)合圖片來理解一下，我們就用示例3的例子進(jìn)行舉例，他的雨水到底代表的是什么。輸入代表的是黃色箱子的個(gè)數(shù)，藍(lán)色箱子代表雨水?dāng)?shù)量?？p隙之間可以裝多少水

上圖則為我們的題目描述，是不是理解了呢？你也可以這樣理解我們?cè)诘厣戏胖昧巳舾筛叨鹊狞S色箱子，他們中間有空隙，然后我們想在他們里面插入若干藍(lán)色箱子，并保證插入之后，這些箱子的左視圖和右視圖都不能看到藍(lán)色箱子。

好啦題目我們已經(jīng)理解了，下面我們看一下解題思路。做這個(gè)題前我們可以先去看一下我們之前做過的另一道題目每日溫度。這兩道題目的思路差不多，都是利用了單調(diào)棧的思想，下面我們來看一下具體思路吧。

這里我們也系統(tǒng)的說一下單調(diào)棧，單調(diào)棧含義就是棧內(nèi)的元素是單調(diào)的，我們這兩個(gè)題目用到的都是遞減棧（相同也可以），我們依次將元素壓入棧，如果當(dāng)前元素小于或等于棧頂元素則入棧，如果大于棧頂元素則先將棧頂不斷出棧，直到當(dāng)前元素小于或等于棧頂元素為止，然后再將當(dāng)前元素入棧。就比如下圖的4，想入棧的話則需要2，3出棧之后才能入棧，因?yàn)?大于他倆。

我們了解單調(diào)棧的含義下面我們來看一下接雨水問題到底該怎么做，其實(shí)原理也很簡單，我們通過我們的例3來進(jìn)行說明。

首先我們依次入棧4，3，2，0我們的數(shù)組前四個(gè)元素是符合單調(diào)棧規(guī)則的。但是我們的第五個(gè)1，是大于0的。那我們就需要0出棧1入棧。但是我們這樣做是為了什么呢？有什么意義呢？別急我們來看下圖。

上圖我們的，4，3，2，0已經(jīng)入棧了，我們的另一個(gè)元素為1，棧頂元素為0，棧頂下的元素為2。那么我們?cè)谶@一層接到的雨水?dāng)?shù)量怎么算呢？2，0，1這三個(gè)元素可以接住的水為一個(gè)單位(見下圖)這是我們第一層接到水的數(shù)量。

注：能接到水的情況，肯定是中間低兩邊高的情況

因?yàn)槲覀冃枰S護(hù)一個(gè)單調(diào)棧，所以我們則需要將0出棧1入棧，那么此時(shí)棧內(nèi)元素為4，3，2，1。下一位元素為1，我們?nèi)霔?，此時(shí)棧內(nèi)元素為4，3，2，1，1。下一元素為5，棧頂元素為1，棧頂?shù)南乱辉厝詾?，則需要再下一個(gè)元素，為2，那我們求當(dāng)前層接到的水的數(shù)量。

注：棧內(nèi)保存的應(yīng)是索引值，這里為了便于理解用了value值

我們是通過2，1，1，5這四個(gè)元素求得第二層的接水?dāng)?shù)為1*3=3;1是因?yàn)閙in(2-1,5-1)=min(1,4)得來的，大家可以思考一下木桶效應(yīng)。裝水的多少，肯定是按最短的那個(gè)木板來的，所以高度為1，3的話是因?yàn)?的索引為6，2的索引為2，他們之間共有三個(gè)元素（3，4，5）也就是3個(gè)單位。所以為6-2-1=3。

將1出棧之后，我們棧頂元素就變成了2，下一元素變成了3，那么3，2，5這三個(gè)元素同樣也可以接到水。

這是第三層的接水情況，能夠接到4個(gè)單位的水，下面我們繼續(xù)出棧2，那么我們的4，3，5仍然可以接到水啊。

這是我們第四層接水的情況，一共能夠接到5個(gè)單位的水，那么我們總的接水?dāng)?shù)加起來，那就是1+3+4+5=13。你學(xué)會(huì)了嗎？別急還有動(dòng)圖我們，我們?cè)賮砩钊肜斫庖还?/span>

接雨水

題目代碼：

class?Solution?{
????public?int?trap(int[]?height)?{
?????????Stack?stack?=?new?Stack();
?????????int?water?=?0;
?????????//特殊情況???????
?????????if(height.length?< 3){
????         return?0;
?????????}???????
?????????for(int?i?=?0;?i??????????????while(!stack.isEmpty()?&&?height[i]?>?height[stack.peek()])???????
?????????????????//棧頂元素
?????????????????int?popnum?=?stack.pop();?
?????????????????//相同元素的情況例1，1?????
?????????????????while(!stack.isEmpty()&&height[popnum]?==?height[stack.peek()]){
?????????????????????stack.pop();
?????????????????}?
?????????????????//計(jì)算該層的水的單位
?????????????????if(!stack.isEmpty()){
?????????????????????int?temp?=?height[stack.peek()];//棧頂元素值????????
?????????????????????//高??????
?????????????????????int?hig?=?Math.min(temp-height[popnum],height[i]-height[popnum]);
?????????????????????//寬
?????????????????????int?wid?=?i-stack.peek()-1;
?????????????????????water?+= hig?*?wid;
?????????????????}

?????????????}???????
?????????????//這里入棧的是索引
?????????????stack.push(i);
?????????}
?????????return?water;
????}
}

這個(gè)題解的圖片太多了，整了挺久，因?yàn)榕吕速M(fèi)了這道經(jīng)典題，所以畫了很多圖片進(jìn)行說明，希望可以幫到大家。下周就是字符串啦，大家加油?。?/span>

我以后每天會(huì)在文章下面放一個(gè)讀者討論（目前還沒有留言功能），大家閱讀完文章消化過之后可以在下面打卡，這樣也算是給自己一個(gè)總結(jié)。另外我以后還會(huì)在文章下面放一個(gè)面試邏輯題，以備不時(shí)之需，大家也可以對(duì)邏輯題進(jìn)行討論。

邏輯題：五個(gè)大小相同的一元硬幣，要求兩兩接觸，應(yīng)該怎么擺？歡迎在留言區(qū)解答！

掃碼關(guān)注【程序IT圈】，讓我們一起領(lǐng)略代碼的魅力吧。長按掃一掃在這里你一定有所收獲。

這就是那個(gè)著名的接雨水算法題詳解

接雨水

題目解析：

題目代碼：