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

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

  • 莫愁
  • 其他
  • 2019-11-22
简介给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
字数 2621.5

题目描述

给定 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的积木为H(0),他左边最高的积木是L(0),右边最高的是R(3),所以该处可以接max(L(0),R(3))-H(0) = 0,

坐标是1的积木为H(1),他左边最高的积木是L(0),右边最高的是R(3),所以该处可以接max(L(0),R(3))-H(1) = -1,由于接的水不能是负数,所以结果是0,

坐标是2的积木为H(0),他左边最高的积木是L(1),右边最高的是R(3),所以该处可以接max(L(1),R(3))-H(0) = 1,

坐标是3的积木为H(2),他左边最高的积木是L(1),右边最高的是R(3),所以该处可以接max(L(1),R(3))-H(2) = -1,由于接的水不能是负数,所以结果是0,

坐标是4的积木为H(1),他左边最高的积木是L(2),右边最高的是R(3),所以该处可以接max(L(2),R(3))-H(1) = 1,

坐标是5的积木为H(0),他左边最高的积木是L(2),右边最高的是R(3),所以该处可以接max(L(2),R(3))-H(0) = 2,

坐标是6的积木为H(1),他左边最高的积木是L(2),右边最高的是R(3),所以该处可以接max(L(2),R(3))-H(1) = 1,

坐标是7的积木为H(3),他左边最高的积木是L(2),右边最高的是R(2),所以该处可以接max(L(2),R(2))-H(3) = -1,由于接的水不能是负数,所以结果是0,

坐标是8的积木为H(2),他左边最高的积木是L(3),右边最高的是R(2),所以该处可以接max(L(3),R(2))-H(2) = 0,

坐标是9的积木为H(1),他左边最高的积木是L(3),右边最高的是R(2),所以该处可以接max(L(3),R(2))-H(1) = 1,

坐标是10的积木为H(2),他左边最高的积木是L(3),右边最高的是R(1),所以该处可以接max(L(3),R(1))-H(2) = -1,由于接的水不能是负数,所以结果是0,

坐标是11的积木为H(1),他左边最高的积木是L(3),右边最高的是R(0),所以该处可以接max(L(3),R(0))-H(1) = -1,由于接的水不能是负数,所以结果是0,

上面加起来就是0+0+1+0+1+2+1+0+0+1+0+0=6;

 

代码思路

上面思路就是找每个积木数的左边和右边最高的积木数,代码实现如下。

PHP代码:

进一步思考,我们其实可以简化成这样:

C++代码:

C代码

其他编程语言大家仿照这个思路来编写,一定会成功的!

该函数时间效率是O(n),空间是O(1)。已经是该问题最优的解法了。


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

文章评论

    • 评论
    人参与,条评论

技术在线

服务时间

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

关闭下雪
关闭背景特效

最新文章