傳言字節面試愛問的「接雨水」怎麽解？

2024-04-22辦公

坊間傳聞，字節面試超愛問「接雨水」演算法題。

今天就帶大家盤一盤這道經典演算法題。如果覺得內容對你有幫助的話麻煩點個贊👍。

一、題目描述

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

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 輸出：6 解釋：上面是由陣列 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部份表示雨水）。

二、題目解析

我們按照行方向去接雨水。

接下來我們去尋找凹槽。

一個凹槽是由三個柱子圍成的 。（這裏為了描述方便，我們把高度為 0 的柱子也當成存在的柱子）

對於這個凹槽來說，它的左側和底部是由棧中挑選出來的，右側是由新添加的柱子決定的。

什麽情況會出現凹槽呢？

一旦新添加的柱子高度大於棧頂元素，就有可能形成凹槽！

這個時候，棧頂元素是凹槽的底部，如果在棧中存在 棧頂元素之前的元素 ，那麽棧頂元素之前的元素就是凹槽的左側，此時添加的元素是凹槽的右側。

這裏之所以是說有可能，是因為柱子裏面可能是兩根高度一樣的柱子，即使新添加的柱子高度都大於它們，也是無法構成凹槽，或者說構成了一個面積為 0 的凹槽。

如果 新添加的柱子高度小於棧頂元素 ，那麽必然無法和當前的棧中元素構成一個凹槽， 因為這是一個單調棧，裏面的元素越靠近棧頂越小，新添加的柱子高度都小於了棧頂元素，那必然小於裏面其它的元素， 這種情況下，無法圍成一個凹槽，我們就把當前的柱子加入到我們的棧中，讓它和裏面的柱子一起等待接下來的柱子。

如果 新添加的柱子高度等於棧頂元素 ，也是無法形成凹槽的，我們就把當前的柱子加入到我們的棧中，讓它和裏面的柱子一起等待接下來的柱子。

一旦形成了凹槽，我們去計算它的面積。

面積由高和寬決定。

凹槽的高度是由 min(凹槽左邊高度, 凹槽右邊高度) - 凹槽底部高度 來計算的。

凹槽的寬度是由 凹槽右邊的下標 - 凹槽左邊的下標 - 1（因為只求中間寬度） 來計算的。

計算完一個凹槽的面積之後，我們就把棧頂元素彈出，觀察 剩下的那些棧中的元素能否和新添加的元素再構成一個新的凹槽 。

三、參考程式碼

# 登入 AlgoMooc 官網獲取更多演算法圖解 # https://www.algomooc.com # 作者：程式設計師吳師兄 # 程式碼有看不懂的地方一定要私聊咨詢吳師兄呀 # 接雨水（ LeetCode 42 ）:https://leetcode-cn.com/problems/trapping-rain-water/ classSolution: deftrap(self, height: List[int]) -> int: # 構建一個棧，用來儲存對應的柱子的下標 # stack 儲存的是下標而非高度 stack = list() # 一開始水的面積是 0 result = 0 # 獲取陣列的長度 n = len(height) # 從頭開始遍歷整個陣列 for i, h in enumerate(height): # 如果棧為空，那麽直接把當前索引加入到棧中 ifnot stack : # 把當前索引加入到棧中 stack.append(i) # 否則的話，棧裏面是有值的，我們需要去判斷此時的元素、棧頂元素、棧頂之前的元素能否形成一個凹槽 # 情況一：此時的元素小於棧頂元素，凹槽的右側不存在，無法形成凹槽 elif height[i] < height[stack[-1]]: # 把當前索引加入到棧中 stack.append(i) # 情況二：此時的元素等於棧頂元素，也是無法形成凹槽 elif height[i] == height[stack[-1]]: # 把當前索引加入到棧中 stack.append(i) # 情況三：此時的的元素大於棧頂元素，有可能形成凹槽 # 註意是有可能形成，因為比如棧中的元素是 2 、2 ，此時的元素是 3，那麽是無法形成凹槽的 else : # 由於棧中有可能存在多個元素，移除棧頂元素之後，剩下的元素和此時的元素也有可能形成凹槽 # 因此，我們需要不斷的比較此時的元素和棧頂元素 # 此時的元素依舊大於棧頂元素時，我們去計算此時的凹槽面積 # 借助 while 迴圈來實作這個操作 while stack and height[i] > height[stack[-1]]: # 1、獲取棧頂的下標，bottom 為凹槽的底部位置 bottom = stack[-1] # 將棧頂元素推出，去判斷棧頂之前的元素是否存在，即凹槽的左側是否存在 stack.pop() # 2、如果棧不為空，即棧中有元素，即凹槽的左側存在 if stack : # 凹槽左側的高度 height[stack[-1] 和凹槽右側的高度 height[i] # 這兩者的最小值減去凹槽底部的高度就是凹槽的高度 h = min(height[stack[-1]], height[i]) - height[bottom] # 凹槽的寬度等於凹槽右側的下標值 i 減去凹槽左側的下標值 stack.top 再減去 1 w = i - stack[-1] - 1 # 將計算的結果累加到最終的結果上去 result += h * w # 棧中和此時的元素可以形成棧的情況在上述 while 迴圈中都已經判斷了 # 那麽，此時棧中的元素必然不可能大於此時的元素，所以可以把此時的元素添加到棧中 stack.append(i) # 最後返回結果即可 return result