您现在的位置是:首页 > 学无止境 > 其他网站首页其他 逻辑算法题,积木接雨水二问题

逻辑算法题,积木接雨水二问题

  • 莫愁
  • 其他
  • 2019-11-23
简介给定一个 m x n 的矩阵,其中的值均为正整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。
字数 5708.5

题目

给定一个 m x n 的矩阵,其中的值均为正整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。

说明:

m 和 n 都是小于110的整数。每一个单位的高度都大于 0 且小于 20000。

示例

给出如下 3x6 的高度图:

[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

返回 4。

rainwater_empty

如上图所示,这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

rainwater_fill

下雨后,雨水将会被存储在这些方块中。总的接雨水量是4。

 

思路

就是将内层数组元素的高度提高到初始数组的最高高度,然后遍历内层的数组元素的上下左右的元素的高度,算出当前元素的最高高度,用while循环遍历,当一个循环内的所有元素的高度都不会变化,则认为已经结束,计算增加的高度及储水量。

 

代码

PHP

 

C++

 

java

 

JavaScript

 

另外一个Java思路

  1. 先将最外围四周看作第一层围栏,矩阵的元素看作节点,将其添加到优先队列中;
  2. 依次出队,并进行bfs,过程中维护一个“当前边界最小值”,该值为所有出队的高度中的最大值;
  3. 在bfs过程中,即访问出队节点的邻居时,若邻居高度小于“当前边界最小值”,则该邻居节点可储水(“当前边界最小值” - 邻居节点高度)
  4. 需要一个visited矩阵,记录bfs遍历过的节点

 


转载: 感谢您对莫愁个人博客网站平台的认可,非常欢迎各位朋友分享到个人站长或者朋友圈,但转载请说明文章出处“来源莫愁个人博客 https://www.mochoublog.com/study/374.html”。

文章评论

    • 评论
    人参与,条评论

技术在线

服务时间

周一至周日 12:00-22:00

关闭下雪
关闭背景特效

最新文章