经典水池接雨水算法

怼烎@ 2023-06-07 10:55 2阅读 0赞

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

![在这里插入图片描述][20191014170117201.png]

上面是由数组 \[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

输入: [2, 0, 2]
    输出: 2

![在这里插入图片描述][20191014170248362.png]

首先，分析一下解题思路：

*  **方案一：按照一层一层统计**  
    **要领**：逐层统计，每层去掉首尾空部分，然后计算中间缺失部分

**第一层**  
取出蓝色模块，2个  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70]

**第二层**  
取出蓝色模块，4个  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 1]

**第三层**  
取出蓝色模块，0个  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 2]  
**代码实现：**

import java.util.*;
    
    /** * @author yanghao * @version LeetCode42Test.java, v 0.1 2019-10-14 16:13 */
    public class LeetCode42Test { 
    
        public static void main(String[] args){ 
            LeetCode42Test test = new LeetCode42Test();
    
            int[] height = new int[]{ 0,1,0,2,1,0,1,3,2,1,2,1};
            //int[] height = new int[]{2, 0, 2};
            System.out.println(test.leetCode42(height));
        }
    
        public int leetCode42(int[] height) { 
    
            //取出最大值
            int max = 0;
            for(int h : height){ 
                if(h > max){ 
                    max = h;
                }
            }
    
            int start = 0;
            int end = 0;
            int pool = 0;
            int all = 0;
    
            //一层一层计算
            for(int storey = 1;storey <= max;storey ++){ 
    
                for(int site = 0;site < height.length;site ++){ 
    
                    if(height[site] >= storey){ 
                        //标记每层开始
                        if(start == 0){ 
                            start = site + 1;
                        }
    
                        //标记每层结束
                        end = site + 1;
    
                    }
    
                    if(height[site] < storey){ 
                        //标记池子数量
                        pool ++;
                    }
    
                }
    
                //计算本层可装水量 = 总池数 - 开头池 - 结尾池
                all += pool - (start - 1) - (height.length - end);
    
                //每层初始化数据
                start = 0;
                end = 0;
                pool = 0;
    
            }
    
            return all;
    
        }

**总结：**  
此方法可以实现最终的目的，而且代码逻辑比较常规，但是循环次数多，如果给的数组足够大和多，代码效率将会很低下。

--------------------

*  **方案二：自左向右统计**  
    **要领1**：从左到右开始，如果右边比左边高，说明已经储水（如下2种情况）  
    **计算公式 = 中间水位个数 \* 最低水位 - 水底柱占用空间（开头0，1可以包含计算）**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 4]

**要领2**：如果左边比右边高，情况有很多，可能就是无法储水了，或者存在更低的储水池（如下3种情况）  
**如果把中间最高位分割之后，右边全部倒置，即可和左边一致计算公式**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 7]

**代码实现：**

import java.util.*;
    
    /** * @author yanghao * @version LeetCode42Test.java, v 0.1 2019-10-11 19:13 */
    public class LeetCode42Test { 
    
        public static void main(String[] args){ 
            LeetCode42Test test = new LeetCode42Test();
    
            int[] height = new int[]{ 0,1,0,2,1,0,1,3,2,1,2,1};
            //int[] height = new int[]{2, 0, 2};
            System.out.println(test.leetCode42(height));
        }
    
        public int leetCode42(int[] height) { 
    
            //从最高峰，分成2个数组
            int max = 0;
            int index = 0;
    
            for(int i = 0; i < height.length; i ++){ 
                if(height[i] > max){ 
                    max = height[i];
                    index = i;
                }
            }
    
            int[] left = new int[index + 1];
            System.arraycopy(height, 0, left, 0, index + 1);
    
            int[] right = new int[height.length - index];
            System.arraycopy(height, index, right, 0, height.length - index);
            //倒置
            for(int i = 0;i < right.length/2; i ++){ 
                int temp = right[i];
                right[i] = right[right.length - 1 -i];
                right[right.length - 1 -i] = temp;
            }
    
            //左边 + 右边
            return getPool(left) + getPool(right);
    
        }
    
        private int getPool(int[] height) { 
            //记录左边位置
            int left = 0;
            //记录实心部分
            int temp = 0;
            //记录总
            int all = 0;
    
            for(int site = 1; site < height.length; site ++){ 
    
                if(height[site] >= height[left]){ 
                    //右边比左边高，记录池水 = 长（剔除两边墙） * 宽 - 实心
                    all += (site - left - 1) * height[left] - temp;
    
                    //左边位置重新标记为右边位置
                    left = site;
    
                    //实心数据初始化
                    temp = 0;
    
                }else{ 
                    //左边比右边高，记录实心数据
                    temp += height[site];
    
                }
    
            }
    
            return all;
    
        }
    }

**总结：**  
此方法效率高，代码执行速度很快，但是理解成本较高，逻辑复杂。

大家可以发挥自己的想象，应该还有更多方式可以写出来～

[20191014170117201.png]: /images/20230601/bc100d7c071945f79b92e1adc3ca8882.png
[20191014170248362.png]: /images/20230601/33a543822a07413986b549344850a755.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70]: /images/20230601/894f411a925a452e82e7f38e96053496.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 1]: /images/20230601/82ed6ab1233f47e78ee9341617fbc5c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 2]: /images/20230601/3793859a86754be19f158310cb1ba51d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 3]: /images/20230601/5722ae1901d24bf782f5f365c58257cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 4]: /images/20230601/11c7239afc774bac8accc63da70fcda7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 5]: /images/20230601/1b1b719169a64750a4cde98e16f9ab51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 6]: /images/20230601/3ebf2ab4ac404133b9f166e0600a5f3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 7]: /images/20230601/ec52852dd04146c892d233b164449d45.png