相关信息
接雨水,这道题最大的问题在于理解怎么才能接到雨水
接雨水其实就是看当前位置的左右是否存在格挡,存在格挡可以存雨水,能存放的最大容积为左右出现的格挡的最大高度
第一步 声明变量初始值 left right maxLeft Maxleft res
第二步 从左右两边开始对比: for left < right {}
第三步 if height[left] < height[right] 则处理左边,否则处理右边
第四步 处理左边 如果当前位置(left)大于等于 maxLeft 则更新maxLeft 否则说明左边的高度是超出当前位置的,可以进行容积增加: maxLeft - height[left]
右边的逻辑和左边一样,发现右边的格挡更高,则增加高度差,否则更新高度最大值(当前值比maxRight更大)
jsfunc trap(height []int) int {
left, right := 0, len(height)-1
leftMax, rightMax := 0, 0
res := 0
for left < right {
if height[left] < height[right] {
if height[left] >= leftMax {
leftMax = height[left]
} else {
res += leftMax - height[left]
}
left++
} else {
if height[right] >= rightMax {
rightMax = height[right]
} else {
res += rightMax - height[right]
}
right--
}
}
return res
}
本文作者:曹子昂
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!