@Author：Runsen

@Date：2020/09/30

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

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

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

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

文章目錄

• Leetcode 42 接雨水
• 常規做法
• 雙指針
• 棧
• 想不到的做法
• 后言（日記）

Leetcode 42 接雨水

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

本題的關鍵點在于，具備什么條件的格子可以存水？

(1) 空間未被柱子占據；(2) 左右兩側均有比當前位置高或者等于的柱子。

其實就是尋找凹陷的地方

知道這個就是好辦了。看看我標題就知道了方法就是棧+雙指針。此題不建議用dp，這種dp還是挺難想的。

常規做法

常規做法就是找到最高的柱子，分成兩份，尋找凹陷的地方。

# @Author：Runsen # @Date：2020/09/30class Solution:def trap(self, height: List[int]) -> int:# 尋找最大的柱子maxindex = maxvalue = 0n = len(height)for i in range(n):if height[i] > maxvalue:maxvalue = height[i]maxindex = i# 左邊找凹槽a = res = 0for i in range(maxindex):if a < height[i]:a = height[i]continueres = res + a - height[i]# 右邊找凹槽b = 0 for i in range(n-1,maxindex,-1):if b < height[i]:b = height[i]continueres = res + b - height[i]return res

雙指針

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

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

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

棧

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

步驟非常簡單：
① 設置一個高度遞減的棧
② 找出先增后減的轉折點的位置
③ 求出那部分凹陷的面積
④ 遍歷，繼續求出其他的面積

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

想不到的做法

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

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

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

當循環結束時，可以發現，我們多加了一個大矩形的面積，
所以最后返回的時候把這個矩形面積減掉就是我們要的結果。

class Solution:def trap(self, height: List[int]) -> int:lmax, rmax, res = 0, 0, 0for 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/

看到這樣的做法，發現自己就是一條菜。今天的算法到了這里差不多了。

后言（日記）

今天看到朋友圈，自己學校的一個大三的舞蹈專業的女學生進了ICU。下面是愛心捐款倡議書，沒錢省吃的我丟了十塊錢。

這里我沒有打碼（愛心人生可以打點錢，錢也不是到我這）.。只是今天我感受到了生命的珍貴，百度上網搜了蛛網膜，發現全是廣告，真的想罵百度了。

蛛網膜下腔出血（subarachnoid hemorrhage，SAH）指腦底部或腦表面的病變血管破裂，血液直接流入蛛網膜下腔引起的一種臨床綜合征，又稱為原發性蛛網膜下腔出血，約占急性腦卒中的10%，是一種非常嚴重的常見疾病。

如果我的分數夠，說不定當年報醫，現在大一跨行敲碼。做醫生受人崇敬，越老越吃香。最后，祝早日康復！

生命的珍貴，前天還跑步摔到了，錢，沒了，可以賺。愛，沒了，可以再找。要有一健康的身體，才是本錢。沒了健康一切都是浮云。

還是趕緊燃燒我的卡路里。Keep打卡堅持，一天博客算法+日記堅持！

老婆再美，你沒了健康，成就了別人
錢財再多，你沒了健康，成就了醫院
不要炫耀你的房，你沒了健康，也是別人的窩
不要炫耀你的車，你沒了健康，也是別人替你開

對了，明天國慶了10月1，我20變成21。現在進入倒計時一個小時，現在是2020/9/30晚上22.56分。雨水問題算法題就當作紀念我從20到21跨步的成長！

我還是當年那個少年！

總結

以上是生活随笔為你收集整理的七十五、栈+双指针，头条当年接雨水问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。