每个柱子上的雨水 = min(柱子左边的最大值,柱子右边的最大值) - height[i]
func trap(_ height: [Int]) -> Int {
var water = 0
let len = height.count
var leftValue = height[0]
var rightArray = Array.init(repeating: 0, count: len)
rightArray[len - 1] = height[len - 1]
for i in (0..<len - 1).reversed() {
rightArray[i] = max(rightArray[i + 1], height[i])
}
for i in 0..<len {
leftValue = max(leftValue, height[i])
water += min(leftValue,rightArray[i]) - height[i]
}
return water
}
最后这种思路比较难想
func trap(_ height: [Int]) -> Int {
let len = height.count
var water = 0 ,lowerMax = 0 ,l = 0 ,r = len - 1
while l < r {
var lower = 0
if height[l] <= height[r] {
lower = height[l]
l += 1
}else {
lower = height[r]
r -= 1
}
lowerMax = max(lowerMax, lower)
water += lowerMax - lower
}
return water
}
网友评论