给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。用JavaScript实现
时间: 2024-02-01 14:14:48 浏览: 19
这个问题可以使用双指针的方法来解决,具体步骤如下:
1. 定义两个指针 left 和 right,分别指向数组的首尾元素,以及两个变量 leftMax 和 rightMax,分别表示左边和右边的最大高度。
2. 定义一个变量 ans 来累加雨水的总量。
3. 当 left <= right 时,进行循环:
1) 如果 leftMax < rightMax,那么说明左边的高度小于右边的高度,此时可以将 left 对应的元素看作一个槽,计算此槽能够接收多少雨水。因为 leftMax 是左边已经遍历过的元素中最高的,所以此槽最多能够接收 leftMax - height[left] 的雨水。更新 leftMax 的值,并将 left 右移一位。
2) 否则,说明右边的高度小于等于左边的高度,此时可以将 right 对应的元素看作一个槽,计算此槽能够接收多少雨水。因为 rightMax 是右边已经遍历过的元素中最高的,所以此槽最多能够接收 rightMax - height[right] 的雨水。更新 rightMax 的值,并将 right 左移一位。
4. 返回 ans。
以下是具体的 JavaScript 代码实现:
```javascript
function trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let ans = 0;
while (left <= right) {
if (leftMax < rightMax) {
ans += Math.max(0, leftMax - height[left]);
leftMax = Math.max(leftMax, height[left]);
left++;
} else {
ans += Math.max(0, rightMax - height[right]);
rightMax = Math.max(rightMax, height[right]);
right--;
}
}
return ans;
}
```
这个算法的时间复杂度是 O(n),空间复杂度是 O(1)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)