LeetCode(Trapping Rain Water) 详解

如图可以看出，就是算出蓝色的区域。（题目来源于 leetcode）

第一个算法时间复杂度是O (log2n)的代码在这里。

我刚开始是这样想的，便利一遍数组找到里面最高的两个柱子，然后计算这两个最高的柱子之间能存多少水。

然后在以这两个柱子为起点向左右两边遍历。以此类推，写一个递归就好了。

当然这个算法可以改一下就变成O（logn）了，因为我在算水的时候是遍历相加的。其实直接用短的柱子*两个柱子的距离+短的柱子与高的柱子的差值。在减去这段距离内的柱子就可以了。不需要遍历（因为你已经便利的这个数组来找到最高的俩个柱子。这个时候算一下柱子的数量就好了）。

第二个算法时间复杂度O（2n）代码在这里

先遍历一遍找到最高的柱子，然后分别从两边开始，往最高的柱子所在位置遍历，水位只会增高不会减小，且一直和最近遇到的最大高度持平，这样知道了实时水位，就可以边遍历边计算面积。

第三个时间复杂度O（n）代码在这里

就是用第一个和最后一个比较一下，你会得到一个短的柱子。用这个开始向另一个遍历。如果遇到一个比自己高的，就用他和另一个高的柱子比较一下。

你又会得到一个短的。然后在向高的遍历。以此类推，在遍历的途中计算水位就OK了，只需要遍历一遍

欢迎大家一起讨论

点击这里可以看到作者的其他文章

欢迎转载，转载请标明出处