# 接雨水问题详解
![](../pictures/souyisou.png) **labuladong 刷题辅助插件上线,欢迎大家使用,[下载地址](https://github.com/labuladong/fucking-algorithm/releases/tag/1.0),别忘了点个 star**~ 读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目: [42.接雨水](https://leetcode-cn.com/problems/trapping-rain-water) **-----------** 接雨水这道题目挺有意思,在面试题中出现频率还挺高的,本文就来步步优化,讲解一下这道题。 先看一下题目: ![](../pictures/接雨水/title.png) 就是用一个数组表示一个条形图,问你这个条形图最多能接多少水。 ```java int trap(int[] height); ``` 下面就来由浅入深介绍暴力解法 -> 备忘录解法 -> 双指针解法,在 O(N) 时间 O(1) 空间内解决这个问题。 ### 一、核心思路 所以对于这种问题,我们不要想整体,而应该去想局部;就像之前的文章写的动态规划问题处理字符串问题,不要考虑如何处理整个字符串,而是去思考应该如何处理每一个字符。 这么一想,可以发现这道题的思路其实很简单。具体来说,仅仅对于位置 `i`,能装下多少水呢? ![](../pictures/接雨水/0.jpg) 能装 2 格水,因为 `height[i]` 的高度为 0,而这里最多能盛 2 格水,2-0=2。 为什么位置 `i` 最多能盛 2 格水呢?因为,位置 `i` 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关,我们分别称这两个柱子高度为 `l_max` 和 `r_max`;**位置 i 最大的水柱高度就是 `min(l_max, r_max)`。** 更进一步,对于位置 `i`,能够装的水为: ```python water[i] = min( # 左边最高的柱子 max(height[0..i]), # 右边最高的柱子 max(height[i..end]) ) - height[i] ``` ![](../pictures/%E6%8E%A5%E9%9B%A8%E6%B0%B4/1.jpg) ![](../pictures/%E6%8E%A5%E9%9B%A8%E6%B0%B4/2.jpg) 这就是本问题的核心思路,我们可以简单写一个暴力算法: ```cpp int trap(vector======其他语言代码====== [42.接雨水](https://leetcode-cn.com/problems/trapping-rain-water) ### java [Yifan Zhang](https://github.com/FanFan0919) 提供 java 代码 **双指针解法**:时间复杂度 O(N),空间复杂度 O(1) 对cpp版本的解法有非常微小的优化。 因为我们每次循环只会选 left 或者 right 处的柱子来计算,因此我们并不需要在每次循环中同时更新`maxLeft`和`maxRight`。 我们可以先比较 `maxLeft` 和 `maxRight`,决定这次选择计算的柱子是 `height[left]` 或者 `height[right]` 后再更新对应的 `maxLeft` 或 `maxRight`。 当然这并不会在时间上带来什么优化,只是提供一种思路。 ```java class Solution { public int trap(int[] height) { if (height == null || height.length == 0) return 0; int left = 0, right = height.length - 1; int maxLeft = height[left], maxRight = height[right]; int res = 0; while (left < right) { // 比较 maxLeft 和 maxRight,决定这次计算 left 还是 right 处的柱子 if (maxLeft < maxRight) { left++; maxLeft = Math.max(maxLeft, height[left]); // update maxLeft res += maxLeft - height[left]; } else { right--; maxRight = Math.max(maxRight, height[right]); // update maxRight res += maxRight - height[right]; } } return res; } } ``` 附上暴力解法以及备忘录解法的 java 代码 **暴力解法**:时间复杂度 O(N^2),空间复杂度 O(1) ```java class Solution { public int trap(int[] height) { if (height == null || height.length == 0) return 0; int n = height.length; int res = 0; // 跳过最左边和最右边的柱子,从第二个柱子开始 for (int i = 1; i < n - 1; i++) { int maxLeft = 0, maxRight = 0; // 找右边最高的柱子 for (int j = i; j < n; j++) { maxRight = Math.max(maxRight, height[j]); } // 找左边最高的柱子 for (int j = i; j >= 0; j--) { maxLeft = Math.max(maxLeft, height[j]); } // 如果自己就是最高的话, // maxLeft == maxRight == height[i] res += Math.min(maxLeft, maxRight) - height[i]; } return res; } } ``` **备忘录解法**:时间复杂度 O(N),空间复杂度 O(N) ```java class Solution { public int trap(int[] height) { if (height == null || height.length == 0) return 0; int n = height.length; int res = 0; // 数组充当备忘录 int[] maxLeft = new int[n]; int[] maxRight = new int[n]; // 初始化 base case maxLeft[0] = height[0]; maxRight[n - 1] = height[n - 1]; // 从左向右计算 maxLeft for (int i = 1; i < n; i++) { maxLeft[i] = Math.max(maxLeft[i - 1], height[i]); } // 从右向左计算 maxRight for (int i = n - 2; i >= 0; i--) { maxRight[i] = Math.max(maxRight[i + 1], height[i]); } // 计算答案 for (int i = 1; i < n; i++) { res += Math.min(maxLeft[i], maxRight[i]) - height[i]; } return res; } } ``` ### javascript **暴力解法** ```js /** * @param {number[]} height * @return {number} */ var trap = function (height) { let n = height.length; let res = 0; for (let i = 1; i <= n - 2; i++) { let l_max = 0, r_max = 0; // 找右边高的柱子 for (let j = i; j < n; j++) { r_max = Math.max(r_max, height[j]) } // 找左边高的柱子 for (let j = i; j >= 0; j--) { l_max = Math.max(l_max, height[j]) } // 如果自己就是最高的话 // l_max == r_max == height[i] res += Math.min(l_max, r_max) - height[i] } return res; }; ``` **备忘录优化** ```js /** * @param {number[]} height * @return {number} */ var trap = function (height) { let n = height.length; if (n <= 2) { return 0; } let res = 0; // 数组充当备忘录 let l_max = new Array(n); let r_max = new Array(n); // 初始化base case l_max[0] = height[0]; r_max[n - 1] = height[n - 1]; // 从左往右算l_max for (let i = 1; i < n; i++) { l_max[i] = Math.max(height[i], l_max[i - 1]) } // 从右往左计算r_max for (let i = n - 2; i >= 0; i--) { r_max[i] = Math.max(height[i], r_max[i + 1]) } // 计算答案 for (let i = 1; i <= n - 2; i++) { res += Math.min(l_max[i], r_max[i]) - height[i]; } return res; }; ``` **双指针解法** ```js /** * @param {number[]} height * @return {number} */ var trap = function (height) { let n = height.length; if (n <= 2) { return 0; } let res = 0; let left = 0; let right = n - 1; let l_max = height[0]; let r_max = height[n - 1]; while (left <= right) { l_max = Math.max(l_max, height[left]); r_max = Math.max(r_max, height[right]); // res += min(l_max, r_max) - height[i] if (l_max < r_max) { res += l_max - height[left]; left++; } else { res += r_max - height[right]; right--; } } return res; }; ```