网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索

 
 
 
日一二三四五六
       
       
       
       
       
       

签到排名:今日本吧第个签到,

本吧因你更精彩,明天继续来努力!

本吧签到人数:0

一键签到
成为超级会员,使用一键签到
一键签到
本月漏签0次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行补签。
连续签到:天  累计签到:天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
08月23日漏签0天
算法吧 关注:30,815贴子:60,105
  • 看贴

  • 图片

  • 吧主推荐

  • 视频

  • 游戏

  • 1回复贴,共1页
<<返回算法吧
>0< 加载中...

求助接雨水算法,像p2这样,下面有转折的怎么办

  • 只看楼主
  • 收藏

  • 回复
  • Saturnnn
  • 新人
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
p1,B站视频的方法对应的坑形状都是直的


  • 瓦妹
  • 新人王
    8
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
先做个假设,列的墙不能是浮空的
首先证明必须得到每个column的所有能放水的格子的信息。能放水的格子,也就是C里面空缺的部分。我们可以设想一下,如果不是C而是E呢?能放水的格子就成了两格。如果是楼层状的呢?所以能放水的格子可能是交错的无限个。比如100高度,奇数高度能放水。因此,我们必须获取每个column里面能放水的格子的信息。
然后第二个问题,我们要如何表示这个信息呢?输入可能这么表示。原本输入是list[int]。每个int表示块状高度。现在块状可能不是连续的,就必须list[(int,int)]。两个int代表从哪到哪是墙。这样我们就能从输入获取形状了
那么获取了形状后如何计算该列的雨水呢?显而易见,如果没有墙,能装的雨水还是老套路,问最高高度=min(左侧最高,右侧最高)。有墙的话,也就是这些list[(int,int)]里面截取低于最高高度的部分求和了
那么我们可以照常左单调,右单调。然后遍历每个列获取列的形状。比如左单调5,右单调8。最高高度等于5。该列形状为[(0,0),(3,4)]。于是得到3-1-0=2的容量,和5-4=1的容量。该列雨水为3
如果有封闭区,或者墙可以浮空。那就很麻烦了。


登录百度账号

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频!
  • 贴吧页面意见反馈
  • 违规贴吧举报反馈通道
  • 贴吧违规信息处理公示
  • 1回复贴,共1页
<<返回算法吧
分享到:
©2025 Baidu贴吧协议|隐私政策|吧主制度|意见反馈|网络谣言警示