收集雨水

题面

给出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 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
133
粉丝
24
喜欢
100
收藏
54
排名:107
访问:8.9 万
私信
所有博文
社区赞助商