leetcode-动态规划-42-接雨水

题目

给定 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

思路

这个问题可以使用双指针和动态规划的方法来解决，以下是使用双指针的解题思路：

1. 我们可以通过遍历一遍数组来找出每个位置的左边最大高度和右边最大高度。

2. 创建两个数组，left_max和right_max，分别记录每个位置左边和右边的最大高度。

3. 对于left_max数组，从左到右遍历数组，left_max[i]表示位置i左边的最大高度。

4. 对于right_max数组，从右到左遍历数组，right_max[i]表示位置i右边的最大高度。

5. 接下来，再次遍历数组，对于每个位置，计算其能接到的雨水量。雨水量可以通过取左右最大高度的较小值，减去当前位置的高度，来计算。

6. 将每个位置的雨水量相加，就得到了总的雨水量。

这种解决方案的时间复杂度是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}
}