Problem Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Analyze
1讨盒、找出最高的柱子，以此柱為中線將數(shù)組分為兩半
2筏餐、處理左邊一半：從左往右計(jì)算柱子高度極大值與當(dāng)前柱子高度差
3鸿秆、處理右邊一半：從右往左同2
Code
class Solution {
func trap(heights: [Int]) -> Int {
let n = heights.count
var water = 0
var max: Int = 0
for (i, value) in heights.enumerate() {
if value > heights[max] {
max = i //找出最高的柱子 將數(shù)組分為兩半
}
}
var peak = 0 // 謹(jǐn)記數(shù)據(jù)越界問題, 不能取heights[0]
for value in heights[0..<max] {
if value < peak {
water += peak - value
}
else if value > peak {
peak = value
}
}
var top = 0
for value in heights[max..<n].reverse() {
if value < top {
water += top - value
}
else if value > top {
top = value
}
}
return water
}
}
