当前位置：首页 > news >正文

LeetCode Hot100 接雨水解题思路详解

news 2026/5/12 15:07:27

LeetCode Hot100：接雨水解题思路详解

题目描述

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

例如，输入height = [0,1,0,2,1,0,1,3,2,1,2,1]，输出为6。

解题思路

这道题的核心思想是：对于每一个位置i，它能够存储的雨水量取决于其左右两侧最高柱子中的较小值与当前柱子高度的差值。

具体步骤如下：

定义状态
- leftMax[i]表示从左端到位置i的最大高度。
- rightMax[i]表示从右端到位置i的最大高度。

预处理左右最大值数组

从左向右遍历，填充leftMax数组：

leftMax[0] = height[0]; for (int i = 1; i < n; i++) { leftMax[i] = Math.max(height[i], leftMax[i - 1]); }

从右向左遍历，填充rightMax数组：

rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { rightMax[i] = Math.max(height[i], rightMax[i + 1]); }

计算每个位置的积水量对于每个位置i，其能接的雨水量为：
```
min(leftMax[i], rightMax[i]) - height[i]
```
将所有位置的积水量累加即可得到答案。
返回结果最终将总和ans返回。

完整代码实现

class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) return 0; int[] leftMax = new int[n]; int[] rightMax = new int[n]; // 构建 leftMax leftMax[0] = height[0]; for (int i = 1; i < n; i++) { leftMax[i] = Math.max(height[i], leftMax[i - 1]); } // 构建 rightMax rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { rightMax[i] = Math.max(height[i], rightMax[i + 1]); } // 计算总积水量 int ans = 0; for (int i = 0; i < n; i++) { ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; } }