网站保障体系建设,广西省河池建设局网站,广州比较好的网站建设公司,垦利网站制作目录
题目来源
题目描述
示例
提示
题目解析
算法源码 题目来源
42. 接雨水 - 力扣#xff08;LeetCode#xff09; 题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 示例1
输入…目录
题目来源
题目描述
示例
提示
题目解析
算法源码 题目来源
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.length1 n 2 * 10^40 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 i1; in; 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 in-2; i0; i--) {// 第 i 根柱子右边最高的柱子要么是h[i1]即第i1根柱子的高度要么是right[i1]即第i1根柱子的右边的最高的柱子的高度right[i] Math.max(right[i1], h[i1]);}int ans 0;for(int i1; in-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 i1; in; 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 in-2; i0; i--) {// 第 i 根柱子右边最高的柱子要么是h[i1]即第i1根柱子的高度要么是right[i1]即第i1根柱子的右边的最高的柱子的高度right[i] Math.max(right[i1], h[i1])}let ans 0for(let i1; in-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: intn 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[i1]即第i1根柱子的高度要么是right[i1]即第i1根柱子的右边的最高的柱子的高度right[i] max(right[i1], h[i1])ans 0for i in range(1, n-1):# 第i根柱子最多能蓄水的量取决于其左边最高的柱子和右边最高的柱子的较矮的那个且较矮的那根柱子 - 第i根柱子的高度就是第i根柱子的蓄水量注意蓄水量最少为0ans max(0, min(left[i], right[i]) - h[i])return ans
