leetcode：42. 接雨水(秒变简单题）

题目要求

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

要求给出一列柱子，求该柱子能盛放多少雨水

解题思路：

这些柱子围城了一个“盆地”，雨水会积攒在低洼处，我们要计算“盆地”能装多少水

关键点：每个位置能接的雨水量，取决于它左右两边最高的柱子中较矮的那个（木桶效应）。

解题步骤分解

找到最高的柱子：

这个柱子把整个区域分成左右两部分
- 左边的水位由左边最高的柱子决定（从左到右遍历到的）
- 右边的水位由右边最高的柱子决定（从右到左遍历到的）

计算左侧雨水：

- 从左往右扫描，记录遇到的最高柱子
- 当前水位就是这个最高柱子的高度
- 每个柱子的积水量 = 当前水位 - 柱子高度

计算右侧雨水：

从右往左扫描，记录遇到的最高柱子
- 当前水位就是这个最高柱子的高度
- 每个柱子的积水量 = 当前水位 - 柱子高度

汇总结果：

把左边和右边的积水量加起来就是总雨水量

其实可以辅助图理解

关键就是我们只需要关注左/右侧最高柱子，因为它是木桶效应中的短板，决定能装多少水

假设这个是最高柱子的左侧，现在我们从1-6开始遍历

1：高度为1，更新左边最高的柱子高度为1，并且计算累计雨水+=（最高柱子-当前柱子高度=0）

2：高度为0，累计雨水+=（最高柱子-当前柱子高度=1）

3：高度为2，更新左边最高柱子高度为1，累计雨水+0

4：高度为1，累计雨水+=（最高柱子2-当前柱子高度1=1）

。。。。

右边也是同理的

java代码实现

class Solution {public int trap(int[] height) {// 1. 首先找到最高的柱子int maxHeight = 0;      // 记录最高柱子的高度int maxPos = -1;        // 记录最高柱子的位置int len = height.length; // 数组长度// 遍历数组，找出最高的柱子及其位置for(int i = 0; i < len; i++) {if(height[i] > maxHeight) {maxHeight = height[i]; // 更新最高高度maxPos = i;           // 更新最高柱子的位置}}// 如果所有柱子高度都为0，接不到雨水if(maxHeight == 0) {return 0;}int sum = 0;            // 总雨水量int waterHeight = 0;    // 当前水位高度// 2. 计算最高柱子左侧的雨水量// 从左往右遍历，水位由左侧最高柱子决定for(int i = 0; i < maxPos; i++) {// 如果当前柱子比之前的水位高，更新水位if(height[i] > waterHeight) {waterHeight = height[i];}// 当前柱子上方的雨水量 = 当前水位 - 当前柱子高度sum += waterHeight - height[i];}// 3. 计算最高柱子右侧的雨水量waterHeight = 0; // 重置水位// 从右往左遍历，水位由右侧最高柱子决定for(int i = len - 1; i > maxPos; i--) {// 如果当前柱子比之前的水位高，更新水位if(height[i] > waterHeight) {waterHeight = height[i];}// 当前柱子上方的雨水量 = 当前水位 - 当前柱子高度sum += waterHeight - height[i];}return sum; // 返回总雨水量}
}