七十五、棧+雙指針，頭條當(dāng)年接雨水問題

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

清晨的時候，熟睡中的我被咯吱咯吱作響的窗子吵醒，起身一看，窗外正是狂風(fēng)大作，不一會兒便下起了爆雨，來也快，去也快，不一會兒天亮便放晴了，院子被雨水洗刷得很干凈，猛的吸一口氣，灌入的是滿鼻的泥土芳香。

不知不覺我唱起了煙花易冷

雨紛紛，舊故里草木深。
我聽聞，你始終一個人。

看著雨水，于是，我打開Leetcode，刷上了Leetcode ?42 ?接雨水。

Leetcode 第42 題 ?接雨水

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

本題的關(guān)鍵點(diǎn)在于，具備什么條件的格子可以存水？

「(1) 空間未被柱子占據(jù)；(2) 左右兩側(cè)均有比當(dāng)前位置高或者等于的柱子?！?/strong>

其實(shí)就是尋找凹陷的地方。

知道這個就是好辦了?？纯次覙?biāo)題就知道了方法就是棧+雙指針。此題不建議用dp，這種dp還是挺難想的。

常規(guī)做法

最樸素的想法是暴力法。針對每一個數(shù)組的值，遍歷數(shù)組以獲得當(dāng)前位置對雨水的貢獻(xiàn)量，這種方式的時間復(fù)雜度為，空間復(fù)雜度為。

就是找到最高的柱子，分成兩份，尋找凹陷的地方，計(jì)算面積即可。

#?@Author：Runsen
#?@Date：2020/09/30

class?Solution:
????def?trap(self,?height:?List[int])?->?int:
??????#?尋找最大的柱子
????????maxindex?=?maxvalue?=?0
????????n?=?len(height)
????????for?i?in?range(n):
????????????if?height[i]?>?maxvalue:
????????????????maxvalue?=?height[i]
????????????????maxindex?=?i
????????#?左邊找凹槽
????????a?=?res?=?0
????????for?i?in?range(maxindex):
????????????if?a?????????????????a?=?height[i]
????????????????continue
????????????res?=?res?+?a?-?height[i]
????????#?右邊找凹槽
????????b?=?0?
????????for?i?in?range(n-1,maxindex,-1):
????????????if?b?????????????????b?=?height[i]
????????????????continue
????????????res?=?res?+?b?-?height[i]
????????return?res

雙指針

雙指針的做法計(jì)算柱子不是一個一個的計(jì)算，而是按照一層一層的算。

我們可以通過左右指針的狀態(tài)，遍歷出來每個高度下的最大接水寬度。當(dāng)左右指針指向的區(qū)域高度小于high時，左右指針都向中間移動，直到指針指向區(qū)域大于等于high的值。若不小于high，則指針不移動。

#?@Author：Runsen
#?@Date：2020/09/30

class?Solution:
????def?trap(self,?height:?List[int])?->?int:
????????n?=?len(height)
????????left,?right?=?0,?n?-?1
????????result,?high?=?0,?1
????????while?(left?<=?right):
?????????#?這里需要注意left?<=?right，如果出現(xiàn)了一層只有一個的情況
????????????while?(left?<=?right?and?height[left]?????????????????left?+=?1
????????????while?(right?>=?left?and?height[right]?????????????????right?-=?1
????????????high?+=?1
????????????result?+=?right?-?left?+?1
????????return?result?-?sum(height)

棧

產(chǎn)生凹陷的地方才能存儲雨水，那么高度一定是先減后增，所以思路就是維護(hù)一個高度遞減的棧。

步驟非常簡單：① 設(shè)置一個高度遞減的棧

② 找出先增后減的轉(zhuǎn)折點(diǎn)的位置

③ 求出那部分凹陷的面積

④ 遍歷，繼續(xù)求出其他的面積

#?@Author：Runsen
#?@Date：2020/09/30

class?Solution:
????def?trap(self,?height:?List[int])?->?int:
????????length=len(height)
????????if?length?3:
????????????return?0
????????res?=?0
????????#?設(shè)置一個高度遞減的棧
????????stack=[]
????????for?index?in?range(0,?length):??#?遍歷index
?????????#?當(dāng)棧>0并且index位置的值>棧里最后的一個元素的值
????????????while?len(stack)>0?and?height[index]?>?height[stack[-1]]:???
?????????????#?彈出棧中最后一個元素
????????????????top=stack.pop()?????
????????????????if?len(stack)?==?0:
????????????????????break
????????????????#?計(jì)算凹陷的高度
????????????????h?=?min(height[stack[-1]],?height[index])?-?height[top]??
????????????????#?計(jì)算凹陷的寬度
????????????????dist?=?index?-?stack[-1]?-?1???
????????????????#?求出存水的量
????????????????res?+=?(dist?*?h)???????
????????????stack.append(index)
????????return?res

想不到的做法

正當(dāng)我用上面三種完成了AC，看了下別人的做法，

想到了一種絕妙的方法，代碼精簡。如下圖所示：

一次循環(huán)中，用左右兩個指針，左指針記錄左邊遇到的最大值，右指針記錄右邊遇到的最大值， 每輪循環(huán)將兩個最大值加起來，并且減去當(dāng)前柱子的高度。

當(dāng)循環(huán)結(jié)束時，可以發(fā)現(xiàn)，我們多加了一個大矩形的面積，所以最后返回的時候把這個矩形面積減掉就是我們要的結(jié)果。

class?Solution:
????def?trap(self,?height:?List[int])?->?int:
????????lmax,?rmax,?res?=?0,?0,?0
????????for?i?in?range(len(height)):
????????????lmax?=?max(lmax,?height[i])
????????????rmax?=?max(rmax,?height[-1-i])
????????????res?+=?lmax?+?rmax?-?height[i]
????????return?res?-?lmax?*?len(height)

我把作者和鏈接寫了上去

作者：821218213
鏈接：https://leetcode-cn.com/problems/trapping-rain-water/solution/42py3liang-chong-fang-fa-yi-ji-xiang-xi-si-lu-by-8/

看到這樣的做法，發(fā)現(xiàn)自己就是一條菜。今天的算法到了這里差不多了。

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?