算法系列之接雨水 _算法

本题来自Leetcode，题目传送门：「链接」
难度：困难
编程语言：Go
1. 题目介绍给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

文章插图
引用自Leetcode

文章插图

提示：
1. n == height.length
2. 1 <= n <=

文章插图
3. 0 <= height[i] <=

文章插图
2. 解题思路要接住雨水，必须形成凹槽。
第一种思路：找到这个柱子左边最高的，和右边最高的，然后计算这个柱子能接到的雨水。量=min(左边最高，右边最高) 。
这种方法下：
1. 每一个柱子都要往两边扩散计算，时间复杂度是O(n)
2. 需要两个额外的数组来保留n个柱子能接到的雨水，空间复杂度为O(n).

第二种思路：寻找比左边高的柱子。当找到凹槽后，可累积的雨水为：超过该高度的面积。比如：
1~~~111*1111111从第四个柱子开始，出现第一个凹槽，可累计的雨水是"*"，宽为1，高为1，累积雨水1个单位。
第五个柱子出现第二个凹槽，其和等高的柱子（第一个柱子）的宽度"～"为3，高为1，所以累积的雨水是3个单位。
图示被丢弃的图样：
111211112从第一个柱子开始，左低右高，无法形成凹槽，丢弃。第三个柱子不能丢弃，因为后面可能存在"2"构成的柱子。第四个柱子同理需要保留，但是同样不累积雨水。
这种方法下：
1. 每一个元素需要入一次栈，时间复杂度为O(n)；
2. 需要一个栈来保存柱子的坐标，最坏情况下保留n个，空间复杂度为O(n)；

第三种思路：由于接到的雨水由左右两个最高的高度的最小值决定，所以可以从左右两侧往中间靠拢，动态的计算左右的最大值。
其中的难点：当从左往右时，左边的最大值是可信的，但是右边的最大值 <= 右边真实的最大值。同理，从右往左也是如此。
这种情况下，如果是从左往右且左边的最大值小于右边的最大值，则该柱子接到的雨水必然等于：左边最大值-当前柱子的高度。同理从右往左，右边最大值小于左边最大值时，也是如此。
则这种情况下，按照相同方向靠拢是可靠的，如从左往右的继续向右计算下一个柱子的累积雨水情况。如果左边最大值小于右边最大值，则右边向左靠拢。
这种方法下：
1. 每一个元素需要一次遍历，时间复杂度为O(n)；
2. 需要保留leftMax和rightMax,空间复杂度为O(1) 。
3. 源码展示先上测试