接雨水-热题 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.length
1 <= 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]
    结束

    返回 接水量
结束