经典水池接雨水算法

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

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

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

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

第一层
取出蓝色模块，2个

第二层
取出蓝色模块，4个

第三层
取出蓝色模块，0个

代码实现：

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可以包含计算）
  

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

代码实现：

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;}
}

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

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