前端刷题路-Day34：接雨水（题号42）

接雨水（题号42）

题目

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

示例 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 个单位的雨水（蓝色部分表示雨水）。 
复制代码

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9
复制代码

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

链接

leetcode-cn.com/problems/tr…

解释

这题啊，这题是有点意外。

自己费劲吧啦就想出一种解法，然后一看答案，好家伙，竟然有3种解法，而且简单清爽。

由于情况的特殊性，DP在这里都不算最优解法，甚至是性能最差的解法。

先说说自己的解法吧，当时看到这题的时候，第一时间就想到的泛洪算法，将整个表当作一个平面直角坐标系的第一象限，划分成单位为1的格子。

柱状图的格子值为1，其余的值为0，然后遍历整个二维数组，再加上一些条件就完事了。

其实想解决这题，重点就是理解可以接水的格子和其他格子的关系，这里不卖官子了，直接说?：

每个格子能接的水主要取决于左右最高的柱子中比较低的那个。

这么说可能比较虚幻，咱们以上面的图标举个例子。

• 第一列

  这一列的左边没有空间了，放弃，接不了水

• 第二列

  这一列左边最高的格子都没有自己的高，所以也接不了水

• 第三列

  左边最高的格子高度是1

  右边最高的格子高度是2

  这里取最低的格子，也就是左边高度为1的格子

  那么此时只需要比较左边最高的格子和当前格子的差即可，这里就是1-0，可以接的水就是1格

• 第四列

  这一列左边最高的格子都没有自己的高，所以接不了水

• 第五列

  左边最高的格子是2

  右边最高的格子是3

  取二者最小值，2

  自身高度为1，所以可以接的水是1

• 第六列

  左边最高的格子是2

  右边最高的格子是3

  取二者最小值，2

  自身高度为0，所以可以接的水是2

• 第七列

  同第五列，可以接的水是1

• 第八列

  左侧没有更高的格子，GG

• 第九列

  左侧最高的格子是3

  右侧没有最高的格子，或者说最高的格子就是自己，GG

• 第十列

  左侧最高的格子是2

  右侧最高的格子是2

  取二者最小值，2

  自身高度为1，所以可以接的水是1

• 第十一列

  右侧没有更高的格子，GG

• 第十二列

  同第十一列，GG

那么这样看下来，可以得出答案是：

1 + 1 + 2 + 1 + 1 = 6
复制代码

那么这里就可以得出关键解法了，想判断第i个格子是否能接水，先找到左右更高的格子，注意这里的更字，如果高度和自身相等也是接不了水的。

如果左右都有比自己的更高的格子，取二者的最小值，减去自身的高度，即可得出当前格子可以接的水量。

下面的三种更好的方法都是依附于这个关键点，如果不理解的话后续的答案可能会看不太懂。

自己的答案（泛洪算法）

function trapF(height) {
  // 初始化变量，获取最大高度
  var len = height.length
      max = Math.max(...height)
      res = 0
  // 开始纵向循环
  for (let i = 0; i < max; i++) {
    // 设置初始值
    var start = false
        tmp = 0
    // 开始横向循环
    for (let j = 0; j < len; j++) {
      /*
        开始计算
        如果开关第一次打开，tmp值为0，res无变化
        如果开关第二次打开，tmp已经在else里进行累计，添加进res
        重置tmp为0
      */
      // 开始计算，如果开关第一次打开
      if (height[j] > i) {
        start = true
        res += tmp
        tmp = 0
      } else {
        // 如果开关已经打开，开始累计tmp
        if (start) tmp++
      }
    }    
  }
  return res
};
复制代码

这里的泛洪算法有些变化，进行了一些优化。

直接去掉了本身的二维数组，因为不需要存储数据了，只需要tmp变量不断累积即可。

首先，获取到数组中的最大值，这就是这个二维数组的上限，循环的时候也是依据这个。

之后就开始循环了，先是纵向循环，数据是一层一层的，之后对每层的数据进行横向循环，获取这个二维数组中的每个元素。

start类似于一个开关，可以想象有这样的一个数组：

[0, 0, 1, 0, 0, 0, 1, 0, 1, 0]
复制代码

一开始循环的时候start为false，所以tmp不会累加。当遇到第一个1的时候，start为true，之后的元素如果是0，则会叠加到tmp上。如果是1的话，将当前的tmp累加到res上，并且重置tmp，开始下一轮叠加。

这一块的比较简单，这里不多做赘述。

这个答案最另外一个一样的题目上是可以过的，但可能是因为这题的测试用例量比较大，所以没过。

时间复杂度是O(n*m)，m是数组中的最大数。

空间复杂度是O(1)。

更好的方法（DP）

万能的DP啊，解决这题也是没问题的。

DP的解法非常简单，主要有3步：

1. 拿到左侧最大数到数组，也就是在每个元素上，当前元素左侧的最大高度
2. 拿到右侧最大数的数组，同1
3. 循环整个数组，判断当前元素的左侧最大数和右侧最大数的关系，进行接水量累积。

?看看代码：

function trapD(height) {
  // 初始化变量
  var len = height.length
      leftMax = new Array(len)
      rightMax = new Array(len)
      res = 0
  // 初始化赋值
  leftMax[0] = height[0]
  rightMax[len - 1] = height[len - 1]
  // 获取完整的leftMax
  for (let i = 1; i < len; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i])    
  }
  // 获取完整的rightMax
  for (let i = len - 2; i > -1; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i])    
  }
  // 开始进行计数操作
  for (let i = 0; i < len; i++) {
    res += Math.min(leftMax[i], rightMax[i]) - height[i]    
  }
  return res
}
复制代码

关键思路和解释里说的一毛一样，需要注意的可能就是leftMax和rightMax数组的初始化赋值吧，别的真没啥里，很简单。

时间复杂度O(n)。

空间复杂度O(n)。

更好的方法（双指针）

这其实是DP解法的增强版，因为在DP解法其实新增了两个数组来存储左侧最大数和右侧最大数。

这里的两个数组其实可以去掉，动态获取也行。

那怎么动态呢？其实就是在遍历到当前元素的时候，同时更新左侧最大数和右侧最大数，同时进行接水量的计算。

如果左侧的最大数比较小，那么久比较左侧最大数和当前左侧元素的差，取到接水量，累计答案。

如果右侧最大值比较小，也是进行相同比较。

?：

function trapD(height) {
  // 初始化变量
  var len = height.length
      left = 0
      right = len - 1
      leftMax = 0
      rightMax = 0
      res = 0
  // 开始挪动指针
  while (left < right) {
    // left、right变化时更新leftMax、rightMax
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])
    // 最小值是左边的数时
    if (height[left] < height[right]) {
      // 进行计算并赋值
      res += leftMax - height[left]
      left++
    } else {
      // 最小值是右边的数时
      res += rightMax - height[right]
      right--
    }
  }
  return res
}
复制代码

利用left和right变量来进行元素定位，left从最左边开始，right从最右边开始。之后进行while循环，实时更新leftMax和rightMax，更新完之后进行大小比较，然后取值即可。

更好的方法（单调栈）

这个确实也还可以，不过思路的话正常人可能会想不到。

核心逻辑感觉上竟然有点类似于笔者的泛洪算法，这里的主要操作的过程是这样的?：

1. 首先，搞一个空数组作为栈，之后开始循环。

2. 每次循环时先判断数组中是否有元素，如果没有元素，并且当前元素不大于数组中最后一个元素，那就啥也不敢，直接往数组中插入当前元素的索引。

3. 如果当前元素大于数组中最后一个元素，那么提取出数组中最后一个元素，如果提取完之后数组就空了，那就跳过，不操作了。

4. 按照上面的例子来说，第一次开始正式操作是在循环到第四个元素的时候，此时的栈是[1, 2]。

5. 那么取出栈中的最后一个元素，也是栈顶的元素——2。

6. 现在开始进行计算，首先取左侧的最大元素，这里也就是栈顶下面的的一个元素，也就是1。右侧的最大元素不用说，也就是当前的元素，索引是i

7. 这里的计算是用块来进行计算的，首先是宽度，这个很好算，直接i - left - 1即可。高度的计算就解释里面的核心算法，两侧最大高度的最小值减去当前的元素的高度。

   需要注意的是这里的当前元素并不是i，而是之前取出的栈顶元素，这里是2。

   所以这一步的值就是?：

   tmpWidth = i - left - 1
   tmpHeight = Math.min(height[i], height[left]) - height[top]
   res += tmpWidth * tmpHeight
   复制代码

   这就完事了，最后还是要把当前的i放到栈里面的，进行后续的循环。

   如此一来，当循环完成时就是取到最终时。

整体代码?：

function trapS(height) {
  // 初始化变量
  var len = height.length
      stack = []
      res = 0
  // 开始循环
  for (let i = 0; i < len; i++) {
    // 如果当前元素大于栈尾元素，开始操作
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      // 取出栈尾元素
      var top = stack.pop()
      // 如果栈就一个元素，GG
      if (!stack.length) break
      /*
        初始化计算变量
        取出当前栈尾元素，也就是top左侧的元素，为left
        获取当前宽度，为tmpWidth
        获取当前的高度，由上面条件可知，height[left]和height[i]都大于height[top]
        所以，也就是left为左侧最大元素，i为右侧最大元素，取两者的最小值再减去height[top]，为tmpHeight
      */
      var left = stack[stack.length - 1]
          tmpWidth = i - left - 1
          tmpHeight = Math.min(height[i], height[left]) - height[top]
      // 计算赋值
      res += tmpWidth * tmpHeight
    }
    stack.push(i)
  }
  return res
}
复制代码

小结

没想到这简单的一题竟然还有这么多解法，是在下输了。

重点还是在于核心思路的理解，这三种解法其实都是基于核心思路的扩散。