原题：接雨水

思路：求每一列上的雨水体积，加起来得到结果

思路

经过简单观察可以得知:

  1. 首先需要找到该列两侧最高的列 maxL 和 maxR

  2. 接着拿两列中较矮的那一列减去当前列高度得到当前列雨水体积 cur = height[i] - min(maxL, maxR)

  3. 得到的结果若大于 0，雨水体积 += 该结果 result += cur

1. 找到该列两侧最高的列

如果根据思路正常的实现，那么每次循环都要从当前列往两侧寻找最高列，非常耗时

为了减少时间复杂度，我们可以用两个数组来存储每个列左右两侧的最高列:

1
2
3
4
5
6
7
const maxL = [];
// 因为 0 在最左侧，直接给下标 0 的左侧最大值设为 0
maxL[0] = 0;

const maxR = [];
// 最后一个下标在最右侧，直接设置其右侧最大值为 0
maxR[height.length - 1] = 0;

根据简单的推导可以得知:

  • 当前列左侧最高列等于 当前列左侧首列 和 其列的左侧最大值 中的 较高列:

    maxL[i] = max(height[i - 1], maxL[i - 1])

  • 当前列右侧最高列等于 当前列右侧首列 和 其列的右侧最大值 中的 较高列:

    maxR[i] = max(height[i + 1], maxR[i + 1])

实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 从 1 开始计算下标左侧最大值
// 要依赖当前下标左侧的值计算，所以从首部开始遍历
// Note: 这里其实可以整合到下一步的遍历中去，为了展现解题思路就放出来
for (let i = 1; i < height.length; i++) {
  // 左侧最大值 = max(上一个下标的值, 上一个下标的左侧最大值)
  maxL[i] = Math.max(maxL[i - 1], height[i - 1]);
}

// 从倒数第二个下标开始计算右侧最大值
// 要依赖当前下标右侧的值计算，所以从尾部开始遍历
for (let i = height.length - 2; i >= 0; i--) {
  // 右侧最大值 = max(下一个下标的值，下一个下标的右侧最大值)
  maxR[i] = Math.max(maxR[i + 1], height[i + 1]);
}

2. 遍历列，计算每一列上的水体积

直接上实现:

1
2
3
4
5
6
7
8
9
10
11
// 遍历每一列，计算当前列上的水体积
for (let i = 1; i < height.length - 1; i++) {
  // 找到左侧最大值和右侧最大值中较小的那个
  const min = Math.min(maxL[i], maxR[i]);
  // 如果最小值大于当前值，证明当前列上存在水
  if (min > height[i]) {
    // 最小值 - 当前值就是水体积
    result += min - height[i];
  }
}
return result;

完整代码

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
44
45
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  // 结果
  let result = 0;

  // 存放指定下标左侧的最大值
  const maxL = [];
  // 因为 0 在最左侧，直接给下标 0 的左侧最大值设为 0
  maxL[0] = 0;

  // 存放指定下标右侧的最大值
  const maxR = [];
  // 最后一个下标在最右侧，直接设置其右侧最大值为 0
  maxR[height.length - 1] = 0;

  // 从 1 开始计算下标左侧最大值
  // 要依赖当前下标左侧的值计算，所以从首部开始遍历
  // Note: 这里其实可以整合到下一步的遍历中去，为了展现解题思路就放出来
  for (let i = 1; i < height.length; i++) {
    // 左侧最大值 = max(上一个下标的值, 上一个下标的左侧最大值)
    maxL[i] = Math.max(maxL[i - 1], height[i - 1]);
  }

  // 从倒数第二个下标开始计算右侧最大值
  // 要依赖当前下标右侧的值计算，所以从尾部开始遍历
  for (let i = height.length - 2; i >= 0; i--) {
    // 右侧最大值 = max(下一个下标的值，下一个下标的右侧最大值)
    maxR[i] = Math.max(maxR[i + 1], height[i + 1]);
  }

  // 遍历每一列，计算当前列上的水体积
  for (let i = 1; i < height.length - 1; i++) {
    // 找到左侧最大值和右侧最大值中较小的那个
    const min = Math.min(maxL[i], maxR[i]);
    // 如果最小值大于当前值，证明当前列上存在水
    if (min > height[i]) {
      // 最小值 - 当前值就是水体积
      result += min - height[i];
    }
  }
  return result;
};