hello 大家好！今天开写一个新章节，每一天一道算法题。让我们一起来学习算法思维吧！
function trap(height) {// 获取柱子数组的长度const n = height.length;// 如果柱子数量小于等于 2，无法形成凹槽接雨水，直接返回 0if (n <= 2) {return 0;}// 初始化两个数组，分别用于记录从左到右和从右到左的最大高度const leftMax = new Array(n).fill(0);const rightMax = new Array(n).fill(0);// 计算从左到右的最大高度leftMax[0] = height[0];for (let i = 1; i < n; i++) {// 当前位置的左最大高度是前一个位置的左最大高度和当前柱子高度的较大值leftMax[i] = Math.max(leftMax[i - 1], height[i]);}// 计算从右到左的最大高度rightMax[n - 1] = height[n - 1];for (let i = n - 2; i >= 0; i--) {// 当前位置的右最大高度是后一个位置的右最大高度和当前柱子高度的较大值rightMax[i] = Math.max(rightMax[i + 1], height[i]);}// 初始化接水量为 0let water = 0;// 遍历每个柱子for (let i = 0; i < n; i++) {// 当前位置能接的雨水量是左右最大高度的较小值减去当前柱子的高度water += Math.min(leftMax[i], rightMax[i]) - height[i];}return water;
}// 示例测试
const height1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
console.log(trap(height1)); const height2 = [4, 2, 0, 3, 2, 5];
console.log(trap(height2));
代码解释
整体思路
要计算柱子能接住的雨水量，对于每个柱子，其能接住的雨水量取决于它左右两侧的最大柱子高度。具体来说，每个柱子能接住的雨水量等于该柱子左右两侧最大高度的较小值减去该柱子自身的高度。因此，我们可以通过以下步骤来解决这个问题：
分别计算每个柱子左侧的最大高度和右侧的最大高度。
遍历每个柱子，根据左右最大高度计算该柱子能接住的雨水量。
将每个柱子能接住的雨水量累加起来，得到总的接水量。
代码步骤分析
边界条件检查：
如果柱子数量小于等于 2，无法形成凹槽来接住雨水，直接返回 0。
计算左右最大高度数组：
leftMax 数组：用于记录从左到右每个位置的最大柱子高度。从左到右遍历柱子数组，每个位置的左最大高度是前一个位置的左最大高度和当前柱子高度的较大值。
rightMax 数组：用于记录从右到左每个位置的最大柱子高度。从右到左遍历柱子数组，每个位置的右最大高度是后一个位置的右最大高度和当前柱子高度的较大值。
计算接水量：
遍历每个柱子，对于每个位置，其能接住的雨水量等于 leftMax[i] 和 rightMax[i] 中的较小值减去 height[i]。
将每个位置的接水量累加起来，得到总的接水量。
