題目描述：給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖揖盘，計算按此排列的柱子眉厨，下雨之后能接多少雨水。
示例：
image
例1
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖扣讼，在這種情況下缺猛，可以接 6 個單位的雨水（藍(lán)色部分表示雨水）。
例2
輸入：height = [4,2,0,3,2,5]
輸出：9
提示：
- n == height.length
- 0 <= n <= 3 * 104
- 0 <= height[i] <= 10^5
以下題解思路來源于LeetCode官方題解
解題語言： Swift
題解一：暴力求解
解題思路：直接按問題描述進(jìn)行椭符。對于數(shù)組中的每個元素荔燎，我們找出下雨后水能達(dá)到的最高位置，等于兩邊最大高度的較小值減去當(dāng)前高度的值销钝。
func trap(_ height: [Int]) -> Int {
if height.count <= 2 {
return 0
}
var ans = 0
let size = height.count
for i in 1..<size - 1 {
var max_left = 0, max_right = 0
//Search the left part for max bar size
for j in (0...i).reversed() {
max_left = max(max_left, height[j])
}
// Search the right part for max bar size
for k in i..<size {
max_right = max(max_right, height[k])
}
ans += min(max_left, max_right) - height[I]
}
return ans
}
復(fù)雜度分析：
時間復(fù)雜度：O(n^2)有咨，數(shù)組中的每個元素都需要向左向右掃描。
空間復(fù)雜度: O(1)的額外空間蒸健。
題解二：動態(tài)規(guī)劃
解題思路：對于下標(biāo) i座享，下雨后水能到達(dá)的最大高度等于下標(biāo) i 兩邊的最大高度的最小值婉商，下標(biāo) i 處能接的雨水量等于下標(biāo) i 處的水能到達(dá)的最大高度減去 height[i]。樸素的做法是對于數(shù)組 height 中的每個元素渣叛，分別向左和向右掃描并記錄左邊和右邊的最大高度丈秩，然后計算每個下標(biāo)位置能接的雨水量。假設(shè)數(shù)組 height 的長度為 n淳衙，該做法需要對每個下標(biāo)位置使用 O(n) 的時間向兩邊掃描并得到最大高度蘑秽，因此總時間復(fù)雜度是 O(n^2)。上述做法的時間復(fù)雜度較高是因?yàn)樾枰獙γ總€下標(biāo)位置都向兩邊掃描箫攀。如果已經(jīng)知道每個位置兩邊的最大高度肠牲，則可以在 O(n) 的時間內(nèi)得到能接的雨水總量。使用動態(tài)規(guī)劃的方法靴跛，可以在 O(n) 的時間內(nèi)預(yù)處理得到每個位置兩邊的最大高度缀雳。創(chuàng)建兩個長度為 n 的數(shù)組 leftMax 和 rightMax。對于 0≤i<n梢睛，leftMax[i] 表示下標(biāo) i 及其左邊的位置中肥印，height 的最大高度, rightMax[i] 表示下標(biāo) i 及其右邊的位置中，height 的最大高度扬绪。顯然竖独，leftMax[0]=height[0]，rightMax[n?1]=height[n?1]挤牛。兩個數(shù)組的其余元素的計算如下：當(dāng) 1≤i≤n?1 時莹痢，leftMax[i]=max(leftMax[i?1],height[i])；當(dāng) 0≤i≤n?2 時墓赴，rightMax[i]=max(rightMax[i+1],height[i])竞膳。因此可以正向遍歷數(shù)組 height 得到數(shù)組 leftMax 的每個元素值，反向遍歷數(shù)組 height 得到數(shù)組 rightMax 的每個元素值诫硕。在得到數(shù)組 leftMax 和 rightMax 的每個元素值之后坦辟，對于 0≤i<n，下標(biāo) i 處能接的雨水量等于 min(leftMax[i],rightMax[i])?height[i]章办。遍歷每個下標(biāo)位置即可得到能接的雨水總量锉走。
動態(tài)規(guī)劃做法可以由下圖體現(xiàn)。
image
class Solution {
func trap(_ height: [Int]) -> Int {
if height.count <= 2 {
return 0
}
let size = height.count
var leftMax = [Int](repeating: -1, count: size)
leftMax[0] = height[0];
for i in 1..<size {
leftMax[i] = max(leftMax[i - 1], height[I]);
}
var rightMax = [Int](repeating: -1, count: size)
rightMax[size - 1] = height[size - 1];
for j in (0...size-2).reversed() {
rightMax[j] = max(rightMax[j + 1], height[j]);
}
var ans = 0
for i in 0..<size {
ans += min(leftMax[i], rightMax[i]) - height[I];
}
return ans
}
}
