给我一份golang的接雨水代码
以下是Golang的接雨水代码:
func trap(height []int) int {
if len(height) == 0 {
return 0
}
leftMax := make([]int, len(height))
leftMax[0] = height[0]
for i := 1; i < len(height); i++ {
if height[i] > leftMax[i-1] {
leftMax[i] = height[i]
} else {
leftMax[i] = leftMax[i-1]
}
}
rightMax := make([]int, len(height))
rightMax[len(height)-1] = height[len(height)-1]
for i := len(height) - 2; i >= 0; i-- {
if height[i] > rightMax[i+1] {
rightMax[i] = height[i]
} else {
rightMax[i] = rightMax[i+1]
}
}
water := 0
for i := 0; i < len(height); i++ {
water += min(leftMax[i], rightMax[i]) - height[i]
}
return water
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
该代码使用动态规划的方法,首先计算每个位置左侧最大高度和右侧最大高度,然后对于每个位置,可以计算出可以接的水量为左侧最大高度和右侧最大高度中较小值减去当前高度。最后将所有位置的接水量求和即可得到总的接水量。
原文地址: https://www.cveoy.top/t/topic/HkH 著作权归作者所有。请勿转载和采集!