收集雨水
0 / 0 / 创建于 4年前 /
pardon110 的个人博客
题面
给出n个数字，表示一个高程图，高程图中每一条的宽度为1，计算下雨之后这个地形可以存储多少水
给出[0,1,0,2,1,0,1,3,2,1,2,1],返回6.
上面的高程图用数组[0,1,0,2,1,0,1,3,2,1,2,1]表示。在这种情况下，6个单位的雨水（蓝色部分）被存储。
输入
[0,1,0,2,1,0,1,3,2,1,2,1]输出
6分析
- 关键 构建V型雨水收集器区间 即左右边界及坑底
- 确保入栈索引对应的高程数据比栈顶小，即为单调递减栈
- 反之出栈，前一栈顶视为坑，出栈后的栈顶视为左边界，当前索引位为右边界
- 计算雨水量，长为当前索引位与当前栈顶位之差，高为两边界之最小峰值与前坑高程之差
上码
func trap( A []int ) int {
var rs int
for i,st :=0,[]int{};i<len(A);{
if len(st)==0 || A[i]<= A[st[len(st)-1]]{
st = append(st,i)
i++
}else{
// 将出栈位视为坑
prev := st[len(st)-1]
st = st[:len(st)-1]
if len(st)>0 {
rs += (i - st[len(st)-1] -1)*( minH(A[i], A[st[len(st)-1]]) - A[prev])
}
}
}
return rs
}
func minH(a,b int)int {
if a < b {
return a
}
return b
}小结
- V型序列数据，大–小–大， 出栈实现顶与底部转化
- 入栈单调递减，否则二选一，出入栈时机，雨水可收集可计算条件
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号