42. 接雨水

开发者 2024-9-11 20:00:16 108 0 来自 中国
42. 接雨水(难度:困难)

标题链接:https://leetcode-cn.com/problems/trapping-rain-water/
标题形貌:

给定 n 个非负整数表现每个宽度为 1 的柱子的高度图,计算按此分列的柱子,下雨之后能接多少雨水。
1.jpg 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表现的高度图,在这种情况下,可以接 6 个单元的雨水(蓝色部分表现雨水)。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6解法一:动态规划法

我们可以,计算每一个位置,对应的左边最大值和右边最大值,即从这个位置,向左看,找到最高块的高度,设为他的左边最大值;同理,向右看,找到右边的最高快的高度,设为他的右边最大值。
左边最大值:
2.jpg 右边最大值:
然后,我们可以计算每块低洼处可以存放的水,就是该位置的左边最大值和右边最大值两个值中的较小值,然后再减去该位置块的高度,就是此位置低洼处的存水量,然后将每个位置的存水量累加,就是末了的结果。
4.jpg 如上图:

  • 在下标为0,左右最大值的较小值为0,此处高度为0,相减得此处的存水量为0;
  • 在下标为1,左右最大值的较小值为1,此处高度为1,相减得此处的存水量为0;
  • 在下标为2,左右最大值的较小值为1,此处高度为0,相减得此处的存水量为1;
  • 在下标为3,左右最大值的较小值为2,此处高度为2,相减得此处的存水量为0;
    ………………
代码:
您需要登录后才可以回帖 登录 | 立即注册

Powered by CangBaoKu v1.0 小黑屋藏宝库It社区( 冀ICP备14008649号 )

GMT+8, 2024-11-26 06:56, Processed in 0.169605 second(s), 35 queries.© 2003-2025 cbk Team.

快速回复 返回顶部 返回列表