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、找出最高的柱子，以此柱为中线将数组分为两半
2、处理左边一半：从左往右计算柱子高度极大值与当前柱子高度差
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 //找出最高的柱子 将数组分为两半
}
}
var peak = 0 // 谨记数据越界问题, 不能取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
}
}
