算法系列之接雨水

2022-08-15 XieYiwen

本题来自Leetcode，题目传送门：「链接」

难度：困难

编程语言：Go

1. 题目介绍

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

引用自Leetcode

提示：

1. n == height.length

2. 1 <= n <=

3. 0 <= height[i] <=

要接住雨水，必须形成凹槽。

第一种思路：找到这个柱子左边最高的，和右边最高的，然后计算这个柱子能接到的雨水。量=min(左边最高，右边最高)。

这种方法下：

1. 每一个柱子都要往两边扩散计算，时间复杂度是O(n)

2. 需要两个额外的数组来保留n个柱子能接到的雨水，空间复杂度为O(n).

第二种思路：寻找比左边高的柱子。当找到凹槽后，可累积的雨水为：超过该高度的面积。比如：

    1  ~  ~  ~  1
    1  1  *  1  1
    1  1  1  1  1

从第四个柱子开始，出现第一个凹槽，可累计的雨水是"*"，宽为1，高为1 ，累积雨水1个单位。

第五个柱子出现第二个凹槽，其和等高的柱子（第一个柱子）的宽度"～"为3，高为1，所以累积的雨水是3个单位。

图示被丢弃的图样：

         1
      1  1     2
   1  1  1  1  2

从第一个柱子开始，左低右高，无法形成凹槽，丢弃。第三个柱子不能丢弃，因为后面可能存在"2"构成的柱子。第四个柱子同理需要保留，但是同样不累积雨水。

这种方法下：

1. 每一个元素需要入一次栈，时间复杂度为O(n)；

2. 需要一个栈来保存柱子的坐标，最坏情况下保留n个，空间复杂度为O(n)；

第三种思路：由于接到的雨水由左右两个最高的高度的最小值决定，所以可以从左右两侧往中间靠拢，动态的计算左右的最大值。

其中的难点：当从左往右时，左边的最大值是可信的，但是右边的最大值 <= 右边真实的最大值。同理，从右往左也是如此。

这种情况下，如果是从左往右且左边的最大值小于右边的最大值，则该柱子接到的雨水必然等于：左边最大值-当前柱子的高度。同理从右往左，右边最大值小于左边最大值时，也是如此。

则这种情况下，按照相同方向靠拢是可靠的，如从左往右的继续向右计算下一个柱子的累积雨水情况。如果左边最大值小于右边最大值，则右边向左靠拢。

这种方法下：

1. 每一个元素需要一次遍历，时间复杂度为O(n)；

2. 需要保留leftMax和rightMax,空间复杂度为O(1)。

先上测试

第一种方法比较简单，此处不实现。

第二种方法：

第三种方法：

Leetcode运算结果

方法二：

方法三：