接雨水问题

男娘i 2022-09-02 07:48 114阅读 0赞

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

![21d9b78465c3806c2a0731a770f160cc.png][]

输入：height = \[0,1,0,2,1,0,1,3,2,1,2,1\]  
输出：6  
解释：上面是由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 注：[题目描述来源于leetcode][leetcode]

题目解析：

一个桶能装多少水是由最短的那块板决定的。如下所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

那对于上面由n个柱子组成的序列，能装多少水也是同样的道理，找出每一个位置左右的最长的柱子，左右最高柱子中短的那根即决定了能装水的量。

分析如下，如下图所示，由5根柱子组成的序列，为了方便表示，我在柱子中间加了空格，想象成紧挨一起的就可以了，要表示阴影柱子所能装水的量

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1][]

其实我们就只需要找柱子左边最大的和柱子右边最大的，如下图中标记的部分。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2][]

当找出左边最大的和右边最大的，其实就可以算出来了。能装水的量，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3][]

那现在问题的关键是，如何能找出每一根柱子左边最长的柱子和右边最长的柱子。 找出之后即可以算出装水量了。接下来讲述几种方法。

**暴力搜索**

代码如下，其实代码也比较简单，都是就是针对每一根柱子循环搜索左边和右边。

public int trap(int[] height) {
    //柱子数少于两根时不会形成桶，自然也装不了水
            if (height == null || height.length <= 2) return 0;
    
            //总装水量
            int sum = 0;
            //i = 1 表示跳过第一根柱子，i < height.length - 1 表示跳过最后一根柱子
            for (int i = 1; i < height.length - 1; i++) {
                //寻找左侧最大的
                int leftMax = 0;
                for (int left = 0; left < i; left++) {
                    if (height[left] > leftMax) {
                        leftMax = height[left];
                    }
                }
    
                //寻找右侧最大的
                int rightMax = 0;
                for (int right = i + 1; right <= height.length - 1; right++) {
                    if (height[right] > rightMax) {
                        rightMax = height[right];
                    }
                }
    
                //装水量取决于短板
                int min = Math.min(leftMax, rightMax);
    
                //最终的装水量其实就是短板减去柱子的高度
                if (min > height[i]) {
                    sum += (min - height[i]);
                }
            }
            return sum;
        }

我们可以看出时间复杂度时O( ![N^\{2\}][N_2] ），空间复杂度时O（1）

我们可以看出时间复杂度是很高的，我们可以采用空间换时间的策略，其实问题的根源是循环找出左右最大柱子时的耗费，那其实我们可以先把这一块先计算，然后保存下来。接下来我们看一种优化方案。

**备忘录**

其实逻辑也比较简单，只需要注意计算左最大时和右最大时遍历顺序的问题，还有边界的处理问题，代码如下：

public int trap(int[] height) {
    //柱子数少于两根时不会形成桶，自然也装不了水
            if (height == null || height.length <= 2) return 0;
    
            //总装水量
            int sum = 0;
    
            //先提前算出
            int[] leftMax = new int[height.length];
            int[] rightMax = new int[height.length];
    
            //初始化
            leftMax[0] = height[0];
            rightMax[height.length - 1] = height[height.length - 1];
    
            //计算leftMax
            for (int i = 1; i < height.length; i++) {
                leftMax[i] = Math.max(leftMax[i - 1], height[i]);
            }
    
            //计算rightMax
            for (int i = height.length - 2; i >= 0; i--) {
                rightMax[i] = Math.max(rightMax[i + 1], height[i]);
            }
    
            //i = 1 表示跳过第一根柱子，i < height.length - 1 表示跳过最后一根柱子
            for (int i = 1; i < height.length - 1; i++) {
                //装水量取决于短板
                int min = Math.min(leftMax[i], rightMax[i]);
    
                //最终的装水量其实就是短板减去柱子的高度
                if (min > height[i]) {
                    sum += (min - height[i]);
                }
            }
            return sum;
        }

这个优化其实和暴力解法思路差不多，就是避免了重复计算，把时间复杂度降低为 O(N)，已经是最优了，但是空间复杂度是 O(N)。

**双指针解法**

双指针解法的套路一般都是一个指针left从前往后遍历，一个指针right从后往前遍历，遍历的过程中根据一定的条件判断是left移动还是right移动，知道left和right相遇。

其实对于接雨水这个问题，也是一样的道理，我们前面暴力解法和基于备忘录的解法已经分析过，我们对于每一个柱子，找到柱子前面最长的柱子和找到柱子后面最长的柱子，然后就可以得出这一根基于这一根柱子为底的桶能装多少水了。

暴力搜索解法的问题根源是遍历过程中寻找左侧最长柱子和右侧最长柱子占据的时间比较大，直接把时间复杂度搞到O（![N^\{2\}][N_2]）。

基于备忘录的解决办法的问题根源是先找出某个位置左侧最长柱子和右侧最长柱子，然后缓存下来，当需要用的时候直接查询，虽然解决了时间复杂度高的问题，但是同时也带来了额外的空间消耗。

基于双指针的解决办法，我们可以利用两个指针，边走边计算。这样既避免了时间的耗费，也解决了额外的空间消耗。

首先针对这个问题我们来写一段双指针大概的模板方法。

private static void flap(int[] height) {
            int leftMax = height[0];
            int rightMax = height[height.length - 1];
            int left = 0;
            int right = height.length - 1;
            while (left <= right) {
                leftMax = Math.max(leftMax, height[left]);
                rightMax = Math.max(rightMax, height[right]);
                left++;
                right--;
            }
        }

双指针移动过程中计算leftMax 和 rightMax，其中leftMax代表height\[0.....left\]的最大值。rightMax代表height\[right........height.length-1\]的最大值。接下来我们基于下面的图来进行分析，其实状态如下，left和right分别指向开始和结束。leftMax的值是5，rightMax的值是4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4][]

**首先记住一个前提，桶能装多少水是由最短的那块板决定的，接下来我们来看下双指针时怎么玩。**

（1）起始时 leftMax > rightMax，那就意味着就目前我们知道的数据，柱子left处能装水的量是由右边决定的，因为我们不知道left右侧right指针指向的位置是不是left指针右侧的最长柱子。但是我们换一个思路。因为 rightMax < leftMax，而且rightMax已经是right指向的柱子右侧的最大值，right柱子能装水的量是由rightMax决定的，而且是已经确定的。原因如下：我们不知道leftMax是否真的就是right柱子左侧的最大值。但是已经确定的leftMax已经大于rightMax了。文字解释比较干燥。

比如下面的图，此时leftMax = 5，rightMax=4，我们知道 leftMax > rightMax ,而rightMax已经是right右侧的最大柱子。所以不管leftMax是否是right柱子左侧的最大值，对结果都无影响。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 5][]

如上图所示，right柱子为底能装水的量就是如下图特殊标注处。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 6][]

（2）其实基于上面的分析，当leftMax小于rightMax是一样的道理，只是此时转而处理left对应的柱子了，第一步处理后，状态如下图，leftMax<rightMax，转而处理left，同时left指向的柱子往右移动

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 7][]

（3）经过第二步的处理，状态如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 8][]

（4）中间省略了几步，经过前面的处理，最终状态变为如下图，此时因为left已经大于right了，不继续处理了，即循环终止条件。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 9][]

经过上面的分析，代码如下：结合上面的分析和代码的注释来看，就比较简单了。

public int trap(int[] height) {
    //柱子数少于两根时不会形成桶，自然也装不了水
            if (height == null || height.length <= 2) return 0;
    
    
            //初始化leftMax、rightMax、left 和 right
            int leftMax = height[0];
            int rightMax = height[height.length - 1];
            int left = 0;
            int right = height.length - 1;
    
            //总装水量
            int sum = 0;
            while (left <= right) {
                //先计算leftMax和rightMax
                leftMax = Math.max(leftMax, height[left]);
                rightMax = Math.max(rightMax, height[right]);
    
                //leftMax < rightMax，则处理left，同时执行left++；
                if (leftMax < rightMax) {
                    sum += (leftMax - height[left]);
                    left++;
                } else {
                    //如果leftMax >= rightMax,则处理right，同时right--；
                    sum += (rightMax - height[right]);
                    right--;
                }
            }
            return sum;
        }

如有错误，麻烦指正，谢谢！

[21d9b78465c3806c2a0731a770f160cc.png]: /images/20220829/f3c88c839ed746bb84be82ef793d22a3.png
[leetcode]: https://leetcode-cn.com/problems/trapping-rain-water
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70]: /images/20220829/b424613a17a9485f951da3d4a0c2c4f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1]: /images/20220829/f6993333d9bd4a4283ab67dc1279f1e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2]: /images/20220829/4957dc5f828a4beabfbb2ea3eb9ef6a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3]: /images/20220829/8ad4cabdd1cf46f19828784ef815977a.png
[N_2]: https://latex.codecogs.com/gif.latex?N%5E%7B2%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4]: /images/20220829/3c3ad4be33084c7d9638a3d80953fd20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 5]: /images/20220829/3c60f1a05b0e40feb5d5e1cd0ca5b058.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 6]: /images/20220829/8c569438c3004a789614b31775af91ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 7]: /images/20220829/9743afb103ee49f590f131ab4fee8c1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 8]: /images/20220829/2162755242fe4b3bad20ffab58726646.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 9]: /images/20220829/e85f6650b01843aebb43e8b38cdb76b2.png