算法：台阶蓄水问题

比眉伴天荒 2021-11-04 13:30 294阅读 0赞

**描述：** 有一组不同高度的台阶，由一个整数数组表示，数组中没个数是台阶的高度，当开始下雨了，台阶之间的水坑会积多少水呢？  
**输入：** 【0，1，0，2，1，0，1，3，2，1，2，1】注：蓝色部分  
**输出：** 6 (PS：红色部分，解释，能存6个单位的水)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjQ0_size_16_color_FFFFFF_t_70]  
**思路一：** 分别从坐向右，从右向左遍历数组，找到每个i的maxLeft和maxRight，再比较min(maxLeft,maxRight),若最小值大于i，则差值为蓄水量。例：横坐标上（3，0）的蓄水量为1。其maxLeft为1，maxRight为2，min(1,2)=1，1-0=1。  
**思路二：** 大体思想同上，只是将两次遍历改为1次，使用指向数组头结点和尾节点的指针分别从左向右和从右向左一次性进行遍历  
**思路三：** 以上都是常规思路，还有一种思路，将数组每个数据以1为单位进行垂直分割，得到n个只有0，1两种高度的台阶，从中匹配1–》n个0（n>=1）《–1（以1开始，1结束，中间n个0）这样的数据段，将每层累加即结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjQ0_size_16_color_FFFFFF_t_70 1]  
如图所示，将数组垂直以1为单位进行分割为n个数组，n为数组中最大值。每个数组中均是0，1，匹配符合以1开始，1结尾，中间n个0，且n>=1这样的数据段，即结果。  
匹配算法可用KMP算法。

**两次遍历：** java

/**
    	 * 台阶蓄水问题
    	 * @param arr
    	 * @return
    	 */
    	public static int solution(int arr[]) {
    		//先求出数组中的最大值，第一次遍历
    		int length = arr.length;
    		int max = 0;//最大值
    		int maxPosition = 0;//最大值对应的数组的下标
    		for (int i = 0;i < length;i++)
    		{
    			if (max < arr[i])
    			{
    				max = arr[i];
    				maxPosition = i;
    			}
    		}
    	 
    		int maxLeft = 0;//从左边开始遍历时的极大值
    		int maxRight = 0;//从右边开始遍历时的极大值
    		int v = 0;//存贮容量
    	 
    		//从左边开始向右遍历到最大值处
    		for(int i = 0;i < maxPosition;i++){
    			//不断更新左边的极大值
    			if (maxLeft < arr[i])
    			{
    				maxLeft = arr[i];
    			}
    			//否则，加上新增加的容积
    			else{
    				v += (maxLeft - arr[i]);
    			}
    		}
    	 
    		//从最右边开始向左遍历到最大值处
    		for(int j = length-1;j > maxPosition;j--){
    			//不断更新右边的极大值
    			if (maxRight < arr[j])
    			{
    				maxRight = arr[j];
    			}
    			//否则，加上新增加的容积
    			else{
    				v += (maxRight - arr[j]);
    			}
    		}
    		return v;
    	}

public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int arr[]= {0,1,0,2,1,0,1,3,2,1,2,1};
    		System.out.println(solution(arr));
    	}

输出：6

> 后记：个人水平有限，如各位读者发现不恰当或错误之处，欢迎提出，以供修改！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjQ0_size_16_color_FFFFFF_t_70]: /images/20211104/35d3bfa206114b558466483ab82612e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjQ0_size_16_color_FFFFFF_t_70 1]: /images/20211104/070625b905f84de1bffba29bca31c43c.png