东莞营销网站建设报价,阿里云服务器部署网站,网站建设的概要设计,威海网络推广公司题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;6 解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1…题目
给定 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 * 104 0 height[i] 105
思路
这个问题可以使用双指针和动态规划的方法来解决以下是使用双指针的解题思路 我们可以通过遍历一遍数组来找出每个位置的左边最大高度和右边最大高度。 创建两个数组left_max和right_max分别记录每个位置左边和右边的最大高度。 对于left_max数组从左到右遍历数组left_max[i]表示位置i左边的最大高度。 对于right_max数组从右到左遍历数组right_max[i]表示位置i右边的最大高度。 接下来再次遍历数组对于每个位置计算其能接到的雨水量。雨水量可以通过取左右最大高度的较小值减去当前位置的高度来计算。 将每个位置的雨水量相加就得到了总的雨水量。
这种解决方案的时间复杂度是O(n)其中n是数组的长度。
代码
object Solution {def trap(height: Array[Int]): Int {val n height.lengthif (n 0) return 0var left 0var right n - 1var leftMax 0var rightMax 0var trappedWater 0while (left right) {if (height(left) height(right)) {if (height(left) leftMax) {leftMax height(left)} else {trappedWater leftMax - height(left)}left 1} else {if (height(right) rightMax) {rightMax height(right)} else {trappedWater rightMax - height(right)}right - 1}}trappedWater}def main(args: Array[String]): Unit {val height1 Array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)println(trap(height1)) // 输出 6val height2 Array(4, 2, 0, 3, 2, 5)println(trap(height2)) // 输出 9}
}
