LeetCode Hot100 接雨水解题思路详解

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

题目描述

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

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

解题思路

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

具体步骤如下：

1. 定义状态

   • leftMax[i]表示从左端到位置i的最大高度。
   • rightMax[i]表示从右端到位置i的最大高度。

2. 预处理左右最大值数组

   • 从左向右遍历，填充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]); }

3. 计算每个位置的积水量对于每个位置i，其能接的雨水量为：

   min(leftMax[i], rightMax[i]) - height[i]

   将所有位置的积水量累加即可得到答案。

4. 返回结果最终将总和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; } }

时间复杂度分析

• 时间复杂度：O(n)，三次线性扫描。
• 空间复杂度：O(n)，使用了两个额外数组leftMax和rightMax。

总结

该方法通过预处理左右最大值，避免了在每个位置重复查找最大值，从而提升了效率。虽然空间复杂度较高，但逻辑清晰，易于理解和实现。

提示：此题还可以用双指针法优化空间复杂度至 O(1)，留作进阶思考。