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