Grimoire

# 42. 接雨水

# 题目

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

# 题解

# 暴力法

记当前位置为 i，该位置左边最大的位置为 l，右边最大的位置为 r，高度数组为 h

那么该位置的接水量是 min(h[l], h[r]) - h[i]

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let sum = 0;
  for (let i = 1; i < height.length - 1; ++i) {
    let max_l = (max_r = 0);
    for (let l = i; l >= 0; l--) {
      max_l = Math.max(height[l], max_l);
    }
    for (let r = i; r <= height.length - 1; r++) {
      max_r = Math.max(height[r], max_r);
    }
    sum += Math.min(max_l, max_r) - height[i];
  }
  return sum;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：双重循环 O(n²) 空间复杂度：O(1)

# 动态规划

上面暴力法需要重复计算左右最大值，实际上可以先遍历计算出左右最大值，然后再遍历一次计算每个位置的接水量

计算左右最大值可通过动态规划得到

左边为例，位置 i 左边的最大值记为 l_max[i]

  • 状态转移方程：l_max[i] = max(l_max(i-1), height[i])
  • 边界条件：l_max[0] = height[0]
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let sum = 0;
  let len = height.length;

  let l_max = [];
  let r_max = [];

  l_max[0] = height[0];
  r_max[len - 1] = height[len - 1];

  // 遍历得到左边最大值
  for (let i = 1; i < len; ++i) {
    l_max[i] = Math.max(l_max[i - 1], height[i]);
  }

  // 遍历得到右边最大值
  for (let i = len - 2; i >= 0; --i) {
    r_max[i] = Math.max(r_max[i + 1], height[i]);
  }

  // 遍历计算结果
  for (let i = 1; i < len - 1; ++i) {
    sum += Math.min(l_max[i], r_max[i]) - height[i];
  }

  return sum;
};
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

时间复杂度：O(n) 空间复杂度：O(n)

# 栈

用栈来保存索引

  1. 栈非空且当前值大于栈顶条形块高度的时候
  • 说明可以接水，弹出栈顶元素
  • 计算当前元素和栈顶距离 dis = cur - st.top() - 1
  • 计算高度 h = min(height[cur], height[st.top()]) - height[top]
  • 更新接水量 sum += dis * h
  1. 栈空直接进入下次循环
  2. 将当前 cur 入栈 继续向右移动 cur
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let sum = 0,
    cur = 0;
  let st = [];
  while (cur < height.length) {
    while (st.length && height[cur] > height[st[st.length - 1]]) {
      let top = st[st.length - 1];
      st.pop();
      if (!st.length) break;
      let dis = cur - st[st.length - 1] - 1;
      let h = Math.min(height[cur], height[st[st.length - 1]]) - height[top];
      sum += dis * h;
    }
    st.push(cur++);
  }
  return sum;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(n) 空间复杂度：O(n)

# 双指针

我们可以认为如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。 我们必须在遍历时维护 l_max 和 r_max ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let sum = 0;

  let l = 0,
    r = height.length - 1;

  let l_max = 0,
    r_max = 0;
  while (l < r) {
    if (height[l] < height[r]) {
      height[l] >= l_max ? (l_max = height[l]) : (sum += l_max - height[l]);
      ++l;
    } else {
      height[r] >= r_max ? (r_max = height[r]) : (sum += r_max - height[r]);
      --r;
    }
  }
  return sum;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：O(n) 空间复杂度：O(1)

← 48. 旋转图像 →