9、接雨水问题

LeetCode：42. 接雨水

题目描述

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

示例 1：

alt text

输入：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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]

输出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

解题思路

我们分析每个柱子能存储的水由什么决定，是比自己高的柱子包围起来
我们可以从左右两边开始，分别找出左右两边最高的柱子，找出较小那个高度，减去自身占用的高度，就是储水高度

来看一张图帮助理解：

代码实现

所有的代码完整实现会放在文末，每种解法旨在说明解法框架，便于理解，也有助于自己动脑思考核心代码实现。

1. 暴力解法

我们遍历柱子，然后从当前柱子往左右去寻找两边最大的柱子，找到这两个柱子后，我们知道水桶效应，能装的水是由较小的那个柱子决定，所以我们可以计算出当前柱子能装多少水，然后加到总的水量中。

暴力解法的代码模板如下：

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let water = 0;
  // 遍历柱子
  for (let i = 1; i < height.length - 1; i++) { 
    // 设置两个指针往左右寻找各自的最大柱子
    let left = i - 1;
    let right = i + 1;
    while(left>=0) { 
      // TODO：如何寻找最大柱子
      // 寻找左侧的最大柱子
      left--
    }
    while(right<height.length) { 
      // TODO：如何寻找最大柱子
      // 寻找右侧的最大柱子
      right++
    }
    // 找到左右两边最大的柱子，计算当前柱子能装多少水,加到总的水量中
     water += Math.min(leftMax, rightMax) - height[i];
  }
  return water;
}

从模板中我们可以看出，暴力解法的时间复杂度是 O(n^2)，空间复杂度是 O(1)，题目虽没有要求，但是无法通过所有的用例,我们需要优化算法，基于这里我们来看动态规划。

2. 动态规划

这个解法也是依赖于暴力解法，我们可以发现，假设最大的柱子是最后一个，那么右侧最大的柱子永远是最后一个，没有必要在每次遍历的时候再去使用右侧指针去遍历，同理左侧也一样。我们可以提前算出每个柱子左右两侧的最大柱子，遍历到的时候直接查询计算即可，我们需要数组来存储左右两侧的最大柱子，来看算法框架：

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
   const n = height.length;
  //  存储左右两侧最大的柱子
  const l_max = new Array(n).fill(0);
  const r_max = new Array(n).fill(0);

  // 使用动态规划类似的方式存储左右两边最大的值
  for (let i = 1; i < n; i++) { 
   //  TODO如何计算左侧最大柱子
  }
  for (let i = n - 2; i >= 0; i--) { 
    //  TODO 如何计算右侧最大柱子
  }
  // 求储水量
  let water = 0;
  for (let i = 0; i < n; i++) { 
    // TODO: 计算当前柱子能装多少水,加到总的水量中
  }
  return water;
}

3. 双指针

双指针解法的思路是，我们从左右两边开始，分别找出左右两边最高的柱子，然后计算出当前柱子能装多少水，然后加到总的水量中。这个解法比较巧妙，最要的思路是，如果要算左边的储水，就比较右边有没有比左边高的柱子，如果没有，右侧指针要往左走，这时候左边大于等于右边，左侧一定有最大值，反之左侧一定也有最大值。

算法框架如下：

/**
 * @param {number[]} height 高度数组
 * @return {number}
 */
var trap = function (height) {
  // 双指针 短板原理
  let left = 0;
  // 右侧指针
  let right = height.length - 1;
  // 左侧最大柱子
  let l_max = 0;
  // 右侧最大柱子
  let r_max = 0;
  // 储水量
  let water = 0;
  // 指针往中间走
  while (left < right) {
    // 保留左侧最大值
    l_max = Math.max(height[left], l_max);
    // 保留右侧最大值
    r_max = Math.max(height[right], r_max);
    // 如果左侧最大值小于右侧最大值，一定是以左边为主，右边不需要再大的值了
    if (l_max < r_max) {
      water += l_max - height[left];
      left++;
    } else {
      // 左侧同理
      water += r_max - height[right];
      right--;
    }
  }
  return water;
};

完整代码

暴力解法动态规划解法双指针解法

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  // 暴力解法
  // 每根柱子能装多少水 取决于左右两边最高的那根柱子
  const n = height.length;
  let waterNums = 0;
  // 遍历水柱
  for (let i = 0; i < n - 1; i++) {
    // 左右找最高点
    let l = i - 1;
    let r = i + 1;
    let leftMax = height[i];
    let rightMax = height[i];
    // 往左移动寻找左侧最大柱子
    while (l >= 0) {
      leftMax = Math.max(leftMax, height[l--]);
    }
    // 往右移动寻找右侧最大柱子
    while (r < n) {
      rightMax = Math.max(rightMax, height[r++]);
    }
    waterNums += Math.min(leftMax, rightMax) - height[i];
  }
  return waterNums;
};

/**
 * @param {number[]} height 高度数组
 * @return {number}
 */
var trap = function (height) {
  const n = height.length;
  const l_max = new Array(n).fill(0);
  const r_max = new Array(n).fill(0);
  // 初始化边界，减少特殊处理
  l_max[0] = height[0];
  r_max[n - 1] = height[n - 1];
  // 使用动态规划类似的方式存储左右两边最大的值
  for (let i = 1; i < n; i++) {
    l_max[i] = Math.max(l_max[i - 1], height[i]);
  }
  for (let i = n - 2; i >= 0; i--) {
    r_max[i] = Math.max(r_max[i + 1], height[i]);
  }
  // 求储水量
  let water = 0;
  for (let i = 0; i < n; i++) {
    water += Math.min(l_max[i], r_max[i]) - height[i];
  }
  return water;
};


/**
 * @param {number[]} height 高度数组
 * @return {number}
 */
var trap = function (height) {
  // 双指针 短板原理
  let left = 0;
  let right = height.length - 1;
  let l_max = 0;
  let r_max = 0;
  let water = 0;
  while (left < right) {
    l_max = Math.max(height[left], l_max);
    r_max = Math.max(height[right], r_max);
    if (l_max < r_max) {
      water += l_max - height[left];
      left++;
    } else {
      water += r_max - height[right];
      right--;
    }
  }
  return water;
};

9、接雨水问题 ​

题目描述 ​

解题思路 ​

代码实现 ​

1. 暴力解法 ​

2. 动态规划 ​

3. 双指针 ​

完整代码 ​