接雨水問(wèn)題

問(wèn)題背景

LeetCode 42. 接雨水
接雨水問(wèn)題是一個(gè)經(jīng)典的計(jì)算雨水滯留量的問(wèn)題，通常使用柱狀圖來(lái)表示不同高度的柱子。在下雨的情況下，柱子之間的凹陷部分能夠存儲(chǔ)雨水，問(wèn)題的目標(biāo)是計(jì)算這些柱子所能接收的雨水總量。

相關(guān)知識(shí)

在解決接雨水問(wèn)題之前，需要了解以下幾個(gè)關(guān)鍵概念：

• 柱狀圖：表示不同高度的柱子，通常由一個(gè)整數(shù)數(shù)組表示，每個(gè)元素代表柱子的高度。
• 雨水滯留：在柱狀圖中，兩根柱子之間的凹陷部分可以存儲(chǔ)雨水，我們需要計(jì)算這些凹陷部分的總?cè)萘俊?/li>

問(wèn)題介紹

給定一個(gè)由非負(fù)整數(shù)表示的柱狀圖，每個(gè)柱子的寬度為 1，計(jì)算這個(gè)柱狀圖可以接收多少雨水。

問(wè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 個(gè)單位的雨水（藍(lán)色部分表示雨水）。

示例 2：

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

輸出：9

解題思路

接雨水問(wèn)題的解決思路通常使用雙指針?lè)?。具體步驟如下：

1. 初始化左指針 left 和右指針 right，并初始化左側(cè)最大高度 leftMax 和右側(cè)最大高度 rightMax 為 0。
2. 使用 left 和 right 指針從兩端向中間遍歷柱子，每次比較 left 和 right 指針?biāo)傅闹痈叨?#xff0c;并更新左側(cè)最大高度 leftMax 和右側(cè)最大高度 rightMax。
3. 如果 height[left] < height[right]，說(shuō)明左側(cè)的最大高度決定了當(dāng)前位置能接收的雨水高度，計(jì)算并累加雨水量，然后將 left 指針向右移動(dòng)一位；否則，右側(cè)的最大高度決定了雨水高度，計(jì)算并累加雨水量，然后將 right 指針向左移動(dòng)一位。
4. 重復(fù)步驟 2 和步驟 3，直到 left 和 right 指針相遇。

最終，累加的雨水量即為所求的雨水滯留量。

代碼實(shí)現(xiàn)

class Solution:def trap(self, height: List[int]) -> int:# 初始化結(jié)果為0res = 0# 初始化左指針left和右指針rightleft, right = 0, len(height) - 1# 初始化左側(cè)最大高度leftMax和右側(cè)最大高度rightMaxleftMax = rightMax = 0# 當(dāng)左指針小于右指針時(shí)，繼續(xù)循環(huán)while left < right:# 更新左側(cè)最大高度leftMaxleftMax = max(leftMax, height[left])# 更新右側(cè)最大高度rightMaxrightMax = max(rightMax, height[right])# 如果左側(cè)當(dāng)前高度小于右側(cè)當(dāng)前高度if height[left] < height[right]:# 計(jì)算當(dāng)前位置能接的雨水量并累加到結(jié)果中res += leftMax - height[left]# 移動(dòng)左指針向右移動(dòng)一位left += 1else:# 否則，計(jì)算當(dāng)前位置能接的雨水量并累加到結(jié)果中res += rightMax - height[right]# 移動(dòng)右指針向左移動(dòng)一位right -= 1# 返回最終結(jié)果return res

上述 Python 代碼實(shí)現(xiàn)了雙指針?lè)ǖ乃悸贰Ｊ紫?#xff0c;我們初始化左指針 left 和右指針 right，以及左側(cè)最大高度 leftMax 和右側(cè)最大高度 rightMax。然后，使用指針從兩端向中間遍歷柱子，計(jì)算并累加雨水量。最后，返回累加的雨水量作為結(jié)果。

時(shí)間和空間復(fù)雜度

• 時(shí)間復(fù)雜度：雙指針?lè)ǖ臅r(shí)間復(fù)雜度為 O(n)，其中 n 是柱子的數(shù)量。
• 空間復(fù)雜度：雙指針?lè)ㄖ恍枰?shù)級(jí)別的額外空間，空間復(fù)雜度為 O(1)。

結(jié)論

接雨水問(wèn)題是一個(gè)經(jīng)典的算法問(wèn)題，通過(guò)雙指針?lè)?#xff0c;我們可以高效地計(jì)算雨水滯留量。