【算法】接雨水
难度：困难
题目
给定 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 * 104
● 0 <= height[i] <= 105
解题思路：
这道题目的核心是求解一个数组中，可以储存多少单位的雨水。想象一下，每个数组元素代表一块宽度为1的柱子高度，雨水会在柱子之间累积。我们要找到所有柱子间的凹陷部分可以储存的雨水总量。
- 初始化：设置两个指针left和right分别指向数组的开始和结束位置，同时初始化两个变量maxLeft和maxRight来跟踪左右两边的最大高度。
- 循环条件：当left < right时，进入循环。
- 更新最大高度：在每一步中，比较当前left和right位置的柱子高度与它们各自方向上的最大高度，更新maxLeft和maxRight。因为雨水的高度受限于两边的最低高度，所以我们只需要关注限制雨水高度的那一边。
- 计算并累加雨水：对于当前位置，雨水的高度是由Math.min(maxLeft, maxRight)决定的，减去当前柱子的高度，就是这部分可以储存的雨水量。累加这部分雨水到总雨水中。
- 移动指针：根据maxLeft和maxRight的大小关系，移动高度较小的那一侧的指针。因为那一侧的柱子高度限制了雨水的高度，移动它可以探索是否有更大的空间储存雨水。
- 重复步骤3-5，直到left >= right。
- 返回结果：最后返回累加的雨水总量。
JavaScript实现：
function trap(height) {
let left = 0, right = height.length - 1;
let maxLeft = 0, maxRight = 0;
let totalRainwater = 0;
while (left < right) {
if (height[left] <= height[right]) {
// 左侧柱子矮或者相等时，更新左侧最大高度并移动left指针
maxLeft = Math.max(maxLeft, height[left]);
totalRainwater += maxLeft - height[left];
left++;
} else {
// 右侧柱子矮时，更新右侧最大高度并移动right指针
maxRight = Math.max(maxRight, height[right]);
totalRainwater += maxRight - height[right];
right--;
}
}
return totalRainwater;
}
// 示例
//console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 输出: 6
使用双指针法解决“计算柱子间雨水量”问题的原因主要在于其高效性和直观性，具体优势如下：
- 效率高：双指针法允许我们在一次遍历中解决问题，只需两个指针分别从数组的两端开始向中间移动，时间复杂度为O(n)，其中n为柱子的数量。相比于其他可能需要多次遍历或使用额外空间的算法，双指针法更加高效。
- 减少空间复杂度：此方法不需要额外的大空间来存储信息，除了几个变量外，几乎不需要额外的空间开销，因此空间复杂度为O(1)，非常节省内存。
- 直观易懂：双指针策略直观地模拟了从数组两端向中心逐步逼近的过程，容易理解。通过比较左右两侧的最大高度并移动较矮一侧的指针，可以直观地看到如何逐步累加雨水量。
- 自动去重：在处理连续相同高度的柱子时，双指针法可以自然地跳过这些柱子，避免了重复计算。例如，当一个指针向内移动时，如果当前柱子高度小于或等于最大高度，直接计算差值并移动指针，不会重复考虑相同高度的柱子。
- 灵活性：双指针法可以适应多种变体问题，比如如果问题变为计算两边高度不同时的雨水量，只需稍作调整即可，体现了算法的灵活性。
原文地址：https://blog.csdn.net/xiaolinlife/article/details/140280211
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！