网站开发费入账,能免费做网站,青岛市城乡和住房建设局,网站没有做适配 怎么办接雨水-热题 100#xff1f;-Lua 中文代码解题第4题
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]
输出#xff1a;6
解释…接雨水-热题 100-Lua 中文代码解题第4题
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
示例 1 输入height [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 个单位的雨水蓝色部分表示雨水。 示例 2
输入height [4,2,0,3,2,5]
输出9
提示
n height.length1 n 2 * 0 height[i]
解题思路
接雨水问题的解决主要依赖于动态规划的思想。这个问题可以理解为求解在一系列柱子中每根柱子能够存储多少雨水。
1. 初始化 - 创建两个数组 left_max 和 right_max 分别记录每根柱子左边和右边的最大高度。 - 对于 left_max初始化时第一根柱子左边的最大高度就是它自身。
2. 计算左右最大值 - 从第二根柱子开始遍历整个柱子序列对于每一根柱子其左侧最大高度是它与前一根柱子中的较大者因为雨水只能被比它高的柱子拦截。 - 同理对右侧最大高度进行计算不过由于我们是从右向左遍历所以需要倒序遍历初始值设置为最后一个柱子的高度。
3. 计算并累加雨水量 - 再次遍历一次柱子序列对于每一根柱子它能储存的雨水量等于它的两侧最大高度中的较小值减去它自身的高度。注意只有当这个差值大于0时才能储存雨水否则高度不够无法存储。
4. 返回结果 - 遍历完成后累计的雨水总量即为所求的答案。
通过以上步骤我们可以有效地避免重复计算并确保找到每根柱子可以储存的最大雨水量最终得到所有柱子总共能接住的雨水总量。
中文代码 -- 无注释版
函数 合计(水坑高度)如果 #水坑高度 0 即返回 0结束局部 n #水坑高度局部 左边高度 {水坑高度[1]}因为 i 2, n 做左边高度[i] 数.最大值(左边高度[i - 1], 水坑高度[i])结束局部 右边高度 {}因为 i n, 1, -1 做右边高度[i] 数.最大值(右边高度[i 1] 或 0, 水坑高度[i])结束局部 接水量 0因为 i 1, n 做接水量 接水量 数.最小值(左边高度[i], 右边高度[i]) - 水坑高度[i]结束返回 接水量
结束-- 示例用法演示
-- 给定一个表示柱子高度的数组调用合计函数计算其容纳雨水总量
接雨水 {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
输出(合计(接雨水))
中文代码 -- 带注释的如下
-- 根据给定高度数组计算容器内可容纳雨水总量
-- 参数 水坑高度 数组表示每个位置柱子的高度信息
-- 返回 返回一个整数表示容器能容纳的雨水总量
函数 合计(水坑高度)-- 若高度数组为空则直接返回0如果 #水坑高度 0 即返回 0结束局部 n #水坑高度-- 初始化并计算每个位置左侧的最大高度局部 左边高度 {水坑高度[1]}因为 i 2, n 做左边高度[i] 数.最大值(左边高度[i - 1], 水坑高度[i])结束-- 计算每个位置右侧的最大高度局部 右边高度 {}因为 i n, 1, -1 做右边高度[i] 数.最大值(右边高度[i 1] 或 0, 水坑高度[i])结束-- 计算每个位置形成的凹槽可容纳雨水量并累加至总水量局部 接水量 0因为 i 1, n 做接水量 接水量 数.最小值(左边高度[i], 右边高度[i]) - 水坑高度[i]结束返回 接水量
结束
这段代码运行后将会输出6
我就想问这样子做代码是不是有点入门水平学生
即可以少做中文注释大家也能看得懂。
