目錄
- 一、題目
- 二、解法
- 完整代碼
一、題目
給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖,計算按此排列的柱子,下雨之后能接多少雨水。
示例 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 個單位的雨水(藍色部分表示雨水)。
示例 2:
輸入:height = [4,2,0,3,2,5]
輸出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
二、解法
可以把水分隔開,相當于m
個水柱,把所有的水柱加在一起就好了。
圖看懂了,接下來就很簡單了,left
數組和right
數組,分別記錄每個點的左邊的最高值,和右邊的最高值
當我們到i的時候,i
左邊的最高值left[i]
就是i-1
時遇到的最高值以及i
的柱子高度
完整代碼
class Solution:def trap(self, height: List[int]) -> int:n = len(height)left = [height[0]] * nright = [height[-1]] * nfor i in range(1, n):left[i] = max(left[i - 1], height[i])right[n - i - 1] = max(right[n - i], height[n - i - 1])res = 0for i in range(n):col = min(left[i], right[i]) - height[i]res += colreturn res