LeetCode - 42 接雨水
目录
题目来源
题目描述
示例
提示
题目解析
算法源码
题目来源
42. 接雨水 - 力扣（LeetCode）
题目描述
给定 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 * 10^4
- 0 <= height[i] <= 10^5
题目解析
本题要计算所有柱子的储水量之和，而这个和其实可以分解求解每一个柱子的储水量。
而一个柱子要想储存住水，则必然在其左边有一根高柱，在其右边也有一根高柱，因为这样才能形成“凹”，才能在中间的低柱子上存储住水。
并且，中间低柱子的储水量取决于，其左边“最高的”柱子，和其右边“最高的”柱子的较矮者，比如下图中：
绿色箭头指向的低柱子的储水量取决于：其左边最高柱子，和其右边最高柱子的较矮者。
因此，本题其实是要我们求解每一根柱子的：
- 左边最高柱子高度
- 右边最高柱子高度
这个求解，可以使用动态规划来做：
我们假设第 i 根柱子的高度为 h[i]，第 i 根柱子的左边最高柱子高度表示为left[ i ]
则第 i 根柱子的左边的最高柱子高度为：
left[ i ] = max( left[ i - 1 ], h[ i - 1 ] )
什么含义呢？
第 i 根柱子左边的最高柱子：
- 要么是 第 i - 1 根柱子，即h[ i - 1 ]
- 要么是 第 i - 1 根柱子的左边的最高柱子，即 left[ i - 1 ]
我们只要从左到右完成left数组的初始化即可。
同理，可得：
right[ i ] = max( right[ i + 1 ], h[ i + 1 ] )
此时需要从右往左完成right数组的初始化。
这样的话，第 i 根柱子的储水量
取决于其左边最高柱子，和其右边最高柱子的较矮者，即min(left[ i ]， right[ i ])
第 i 根柱子的储水量val = min(left[ i ]， right[ i ]) - h[ i ]
注意val最小为0，不能为负数。因此最终第 i 根柱子的储水量计算公式为：
max(0, min(left[ i ]， right[ i ]) - h[i])
我们只要累加每根柱子的储水量即为题解。
Java算法源码
class Solution {public int trap(int[] h) {int n = h.length;// left[i] 表示 第 i 根柱子的左边的最高的柱子的高度int[] left = new int[n];for(int i=1; i<n; i++) {// 第 i 根柱子左边最高的柱子要么是h[i-1]，即第i-1根柱子的高度，要么是left[i-1]，即第i-1根柱子的左边的最高的柱子的高度left[i] = Math.max(left[i-1], h[i-1]);}// right[i] 表示 第 i 根柱子的右边的最高的柱子的高度int[] right = new int[n];for(int i=n-2; i>=0; i--) {// 第 i 根柱子右边最高的柱子要么是h[i+1]，即第i+1根柱子的高度，要么是right[i+1]，即第i+1根柱子的右边的最高的柱子的高度right[i] = Math.max(right[i+1], h[i+1]);}int ans = 0;for(int i=1; i<n-1; i++) {// 第i根柱子最多能蓄水的量，取决于其左边最高的柱子和右边最高的柱子的较矮的那个，且较矮的那根柱子 - 第i根柱子的高度就是第i根柱子的蓄水量，注意蓄水量最少为0ans += Math.max(0, Math.min(left[i], right[i]) - h[i]);}return ans;}
}
JS算法源码
/*** @param {number[]} height* @return {number}*/
var trap = function(h) {const n = h.length// left[i] 表示 第 i 根柱子的左边的最高的柱子的高度const left = new Array(n).fill(0)for(let i=1; i<n; i++) {// 第 i 根柱子左边最高的柱子要么是h[i-1]，即第i-1根柱子的高度，要么是left[i-1]，即第i-1根柱子的左边的最高的柱子的高度left[i] = Math.max(left[i-1], h[i-1])}// right[i] 表示 第 i 根柱子的右边的最高的柱子的高度const right = new Array(n).fill(0)for(let i=n-2; i>=0; i--) {// 第 i 根柱子右边最高的柱子要么是h[i+1]，即第i+1根柱子的高度，要么是right[i+1]，即第i+1根柱子的右边的最高的柱子的高度right[i] = Math.max(right[i+1], h[i+1])}let ans = 0for(let i=1; i<n-1; i++) {// 第i根柱子最多能蓄水的量，取决于其左边最高的柱子和右边最高的柱子的较矮的那个，且较矮的那根柱子 - 第i根柱子的高度就是第i根柱子的蓄水量，注意蓄水量最少为0ans += Math.max(0, Math.min(left[i], right[i]) - h[i])}return ans
};
Python算法源码
class Solution(object):def trap(self, h):""":type height: List[int]:rtype: int"""n = len(h)# left[i] 表示 第 i 根柱子的左边的最高的柱子的高度left = [0]*nfor i in range(1, n):# 第 i 根柱子左边最高的柱子要么是h[i-1]，即第i-1根柱子的高度，要么是left[i-1]，即第i-1根柱子的左边的最高的柱子的高度left[i] = max(left[i-1], h[i-1])# right[i] 表示 第 i 根柱子的右边的最高的柱子的高度right = [0]*nfor i in range(n-2,0,-1):# 第 i 根柱子右边最高的柱子要么是h[i+1]，即第i+1根柱子的高度，要么是right[i+1]，即第i+1根柱子的右边的最高的柱子的高度right[i] = max(right[i+1], h[i+1])ans = 0for i in range(1, n-1):# 第i根柱子最多能蓄水的量，取决于其左边最高的柱子和右边最高的柱子的较矮的那个，且较矮的那根柱子 - 第i根柱子的高度就是第i根柱子的蓄水量，注意蓄水量最少为0ans += max(0, min(left[i], right[i]) - h[i])return ans