Leecode42：接雨水

本文主要是介绍Leecode42：接雨水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一反应是按照高低这个思路来求解，因为可以把盛雨水的容器想成是从左往右的，遇到一个沟就存一点雨水。

这个思路

看了下题解，发现自己的思路其实没问题，确实是按照最高最低来求，但是这个地方太复杂了求的，每一格单独求才现实。

修改后成功ac，主要注意两点：一是最左端别忘记取，二是别忽视了可能中间的这个是最高的，导致不加一个判断条件的话会导致每列都被计算从而出现负值。

这个方法的时间复杂度为O(N2)，空间复杂度为O(1)。

方法2：动态规划

这个方法和上面的思路不太一样，有点“以空间换时间”的感觉，它的时间复杂度为O(N)，空间复杂度为O(N)，ac代码如下：

方法3：双指针

这边就是因为很多left_max和right_max都不会被用到。所以实际上一个未知数就可以存储结果了（每次判断当前的值和之前的值是否有区别）。这里有问题是没有明白动态规划的思想（即从前往后、从后往前，这里都是从前往后所以就是错误的）。

。

height [ left - 1] 是可能成为 max_left 的变量， 同理，height [ right + 1 ] 是可能成为 right_max 的变量。

只要保证 height [ left - 1 ] < height [ right + 1 ] ，那么 max_left 就一定小于 max_right。

因为 max_left 是由 height [ left - 1] 更新过来的，而 height [ left - 1 ] 是小于 height [ right + 1] 的，而 height [ right + 1 ] 会更新 max_right，所以间接的得出 max_left 一定小于 max_right。

反之，我们就从右到左更。

下面的错因：记住，值的判断之和left、right位置的有关，而和i无关！！

下面是使用双指针法的ac代码，这里的时间复杂度为O(N)，空间复杂度为O(1)。

这篇关于Leecode42：接雨水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---