给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

思路

  1. 找到峰值所在下标,雨水总体积 = 下标左侧雨水体积 + 下标右侧雨水体积
  2. 以左侧为例,从左到右遍历,遍历找到 m 个阶段峰值,将相邻峰值柱子间的雨水体积累加即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var trap = function (items) {
let peakIndex = 0
let maxVal = -1
for (let i = 0; i < items.length; ++i) {
if (items[i] > maxVal) {
maxVal = items[i]
peakIndex = i
}
}

let sum = 0
{
let left = 0
let right = left
while (right <= peakIndex) {
while (right + 1 <= peakIndex && items[right + 1] < items[left]) {
++right
}
++right
const curHeight = Math.min(items[left], items[right])
for (let i = left + 1; i < right; ++i) {
sum += curHeight - items[i]
}
left = right
}
}
{
let right = items.length - 1
let left = right
while (left >= peakIndex) {
while (left - 1 >= peakIndex && items[left - 1] < items[right]) {
--left
}
--left
const curHeight = Math.min(items[left], items[right])
for (let i = left + 1; i < right; ++i) {
sum += curHeight - items[i]
}
right = left
}
}
return sum
}