題目描述：
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖臊岸，計(jì)算按此排列的柱子址否，下雨之后能接多少雨水占婉。
接雨水題目描述.png
上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖酒请，在這種情況下量愧，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）。 感謝 Marcos 貢獻(xiàn)此圖溃槐。
示例:
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
解題思路：
思路一匣砖，時(shí)間復(fù)雜度由希爾排序決定，最大N*logN昏滴，以[90,100,56,10,0,80,30,60]為例：
- 降序數(shù)組猴鲫，數(shù)組內(nèi)容為值及對應(yīng)的原始位置（location，value）[(1,100),(0,90),(5,80),(7,60),(2,56),(6,30),(3,10),(4,0)]
- 遍歷排序后的數(shù)組谣殊，根據(jù)能夠接水的必要條件是兩個(gè)柱子之間必須有間隙拂共，即不能相鄰，拿到可以接水的區(qū)間:
- 100跟90之間沒有間隙姻几，找下一個(gè)宜狐；
- 100跟80之間有間隙势告，符合可以接水的必要條件，存儲(chǔ)該區(qū)間gap =（1抚恒，5）咱台，并計(jì)算該區(qū)間可以接水的量:遍歷區(qū)間（2～4）內(nèi)的數(shù)據(jù)container += min(100,80) - arr[i];
- 繼續(xù)循環(huán)，看是否在gap區(qū)間對應(yīng)（0俭驮，6）范圍內(nèi)（其中0和6回溺，如果在，由于已經(jīng)計(jì)算表鳍，continue），80不再區(qū)間祥诽，根據(jù)位置關(guān)系更新gap為（1譬圣，7），計(jì)算新增區(qū)間（5雄坪，7）可以接水的量container += min(100,80) - arr[i]厘熟；
-
比較gap區(qū)間跟整個(gè)數(shù)組范圍（1，count -2）關(guān)系维哈，如果小于等于gap绳姨，計(jì)算完畢，沒有繼續(xù)c步驟阔挠。 思路一.png
代碼如下：
static func trap(_ height: [Int]) -> Int {
if height.count <= 2 {
return 0
}
let sortHeight = sortArr(arr: height)///降序飘庄，拿到值及對應(yīng)的原始位置 [(原始位置，值)]
var container = 0
var gap :(Int,Int)?
for k in 0..<sortHeight.count-1 {
let firstL = sortHeight[k]
guard let gugap = gap else {
var i = k+1
while (gap ?? nil) == nil && i < sortHeight.count{///從最大值（如果不是最大值開始购撼，可能漏算）開始跪削，拿到第一段可以接水的區(qū)間。
let secondL = sortHeight[I]
if abs(firstL.0 - secondL.0) > 1 { ///可以接水的必要條件是迂求，兩個(gè)柱子之間有間隙
let start = min(secondL.0, firstL.0)
let end = max(secondL.0, firstL.0)
gap = (start,end)///保存區(qū)間
for g in start + 1...end-1 {///計(jì)算此區(qū)間可以接水的量
container += secondL.1 - height[g] < 0 ? 0:secondL.1 - height[g]///雖然中間有間隔碾盐，但是不能保證能接水，去掉不能接水揩局，即中間的柱子不是最小
}
if start <= 1 && end >= sortHeight.count - 2{
return container
}
}
i += 1
}
continue
}
if firstL.0 <= gugap.1 + 1 && firstL.0 >= gugap.0 - 1 {///在已經(jīng)結(jié)算的區(qū)間內(nèi)毫玖，continue
continue
}else{///不再已經(jīng)結(jié)算的區(qū)間，根據(jù)位置關(guān)系凌盯，更新結(jié)算區(qū)間
var start = 0
var end = 0
if firstL.0 > gugap.1 {///在右邊
start = gugap.1
end = firstL.0
gap = (gugap.0,end)
}else{///在左邊
start = firstL.0
end = gugap.0
gap = (start,gugap.1)
}
for g in start + 1...end-1 {///計(jì)算新增區(qū)間可以接水的量付枫，同樣可能會(huì)有不能接水的可能，剔除
container += firstL.1 - height[g] < 0 ? 0:firstL.1 - height[g]
}
if start <= 1 && end >= sortHeight.count - 2{
return container
}
}
}
return container
}
static func sortArr(arr:[Int]) -> [(Int,Int)] {///希爾排序
let count = arr.count
var locValueTump :[(Int,Int)] = []
for i in 0..<count {
locValueTump.append((i,arr[i]))///記錄位置及對應(yīng)的值
}
var gap = count/2
while gap > 0 {
for i in gap..<count{
var j = I
let temp = locValueTump[j]
if locValueTump[j].1 > locValueTump[j-gap].1 {
while j-gap>=0 && temp.1 > locValueTump[j-gap].1 {
locValueTump[j] = locValueTump[j-gap]
j -= gap
}
locValueTump[j] = temp
}
}
gap /= 2
}
return locValueTump
}
思路二驰怎，比較暴力時(shí)間復(fù)雜度O(n^2)：
- 從數(shù)組的第二個(gè)元素開始到倒數(shù)第二個(gè)元素遍歷励背，，向左向右分別取到最大值max_left,max_right砸西；
-
計(jì)算接水量 container += min(max_left,max_right) - height[I]叶眉。思路二.png
static func trap(_ height: [Int]) -> Int {
if height.count <= 2 {
return 0
}
var ans = 0;
let size = height.count;
for i in 0..<size - 1 {//向左尋找最大
var max_left = 0, max_right = 0;
for j in 0...i { //Search the left part for max bar size
max_left = max(max_left, height[j]);
}
for j in i..<size { //向右邊查找最大值
max_right = max(max_right, height[j]);
}
ans += min(max_left, max_right) - height[i];
}
return ans;
}
