【刷题日记】42. 接雨水

本次刷题日记的第 14 篇，力扣题为：42. 接雨水 ，困难

一、题目描述：

乍一看这个题，题目表示也很简单清晰明了，可却是一个困难题

难道题目表述越少，题目越困难？不过应该没事吧，我们上一篇刷了【刷题日记】11. 盛最多水的容器 ， 看上去这两个题目有点像，我们肯定能解决，来一起看看

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

没关系大兄弟，啥题咱都能解，哪怕一时半会解不了，我们也可以研究，向别人请教，最终我们总能解决，相信自己

工作中也是一样，摆正态度，遇到问题，多加思考背后的逻辑和原理，争取以后能够解决掉所有同样类型的问题

开始来看看这道题给我们展示了哪些重要的信息：

• 第一，这是一个困难题，我们应该尽可能的考虑全面，不要有心里压力
• 第二，这也是一个计算容积的问题，和上一道 【刷题日记】11. 盛最多水的容器 有些许区别，但是取决于是否能够承接雨水，还是要看短板
• 此处我们需要注意题目给出数组的长度 n 的范围是 1 -- 10 的 4 次方

我们是否会这样思考去计算接雨水？

从左到右遍历，当右边比左边高的时候，计算高低差值，然后减去过程中的柱子高度

但是发现，其实逻辑这么纯粹是有问题的，因为右边的柱子并不都左边高，反之亦然，发现上图中，按照纯粹的逻辑是走不通的，中间可能存在我们考虑不周的场景和逻辑

那么我们思考一下，如果我们能有办法直接计算出某一列他能接多少单位的雨水，这样一来，处理起来岂不是更明确了？

如何来计算当前列到底能承接多少雨水呢？

还是这个原理，一个桶能装多少水，取决于短板，那么当前列是否可以承接雨水，能承接多少雨水，也取决于当前列，是否比左边和比右边短

则，我们可以看到如下的图演示

通过查看上图演示，我们知道当前列能承接多少雨水，只需要计算当前列的最左边的身高，最右边的身高，得到他们的最小值之后，再减去当前列自己的身高，即可计算出来

那么接下来，咱们就来简单的实现一下上述的思想吧，这个逻辑就很明确了，按照列来计算承接的雨水，然后对所有列求和

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func trap(height []int) int {
    // 计算每一列左边的最大高度
    leftMax := make([]int, length)
    leftMax[0] = height[0]
    for i:=1; i< length-1; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }
    // 计算每一列右边的最大高度
    rightMax := make([]int, length)
    rightMax[length-1] = height[length-1]
    for i:=length - 2; i>= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }
    // 计算当前列的实际雨水单位数
    res := 0
    for i,h := range height {
       tmp := min(leftMax[i],rightMax[i])
       if tmp > h{
           // 当前列是短板的时候，才能承接雨水
            res += tmp - h
       }
    }
    return res
}
func max(a,b int)int{
    if a>b {
        return a
    }
    return b
}
func min(a,b int)int{
    if a<b {
        return a
    }
    return b
}

上述就是根据思路实现的代码，思路清晰了，编码就是一个翻译的过程，考虑好各种场景，咱们实现起来就比较顺畅，可以减少返工和出现 bug 的风险

四、总结：

这题的时间复杂度和空间复杂度都是 O(n)，原因是我们只需要遍历一次 height 数组，且我们引入的O(n) 级别的空间消耗

原题地址：42. 接雨水

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~