2019-10-08

接雨水

题目

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

　
示例:
　输入: [0,1,0,2,1,0,1,3,2,1,2,1]
　输出: 6

解题思路：

在乘更多的水的题目基础下，此题需解决每个格子怎么确定接水量。
通过分析，每个格子左边和右边的最大值中哪个小一点就会影响接水量（受最小值影响），因此我们确定两个指针i和j用来移动得出每个格子的接水量，而定义leftmax和rightmax为当前格子左边和右边的最大值。
　分为两个情况：
（1）如果左边的最大值<右边的最大值，那么就要确定左边i指针指向的格子接水量（leftmax-height[i]）
（2）如果左边的最大值>=右边的最大值，那么就要确定右边j指针指向的格子接水量（rightmax-height[j]）

方法：双指针法

代码(根据力扣官网提交作品的格式)：

class Solution {
        public int trap(int[] height) {
           int max=0,leftmax=0,rightmax=0;
           int i=0;
           int j=height.length-1;
           while(i<j)
           {
        	   leftmax=Math.max(leftmax, height[i]); //更新为左边最大值
        	   rightmax=Math.max(rightmax, height[j]); //更新为右边最大值
        	   if(leftmax<rightmax) //如果左边最大值小于右边最大值，左边就为限制因素
        	   {
        		   max+=leftmax-height[i]; //接水量=左边最大值-当前格子值
        		   i++; //指针后移，计算下一个格子
        	   }
        	   else //如果左边最大值大于等于右边最大值，右边就为限制因素
        	   {
        		   max+=rightmax-height[j]; //接水量=右边最大值-当前格子值   
        		   j--; //指针前移，计算前一个格子
        	   }
        	   
           }
              return max;
	    }
}

完整代码：

import java.util.Scanner;
public class Solution{
	public static void main(String[] args) {
	   Scanner input=new Scanner(System.in);
	   int n=input.nextInt();
	   int[] a=new int[n];
	   for(int w=0;w<a.length;w++)
	   {
		   a[w]=input.nextInt();  //输入n个柱状
	   }   
	    System.out.println(trap(a));  //输出接水量	   
	}	   
		public static  int trap(int[] height) {
           int max=0,leftmax=0,rightmax=0;
           int i=0;  //从首部开始
           int j=height.length-1;  //从尾部开始
           while(i<j)  
           {
        	   leftmax=Math.max(leftmax, height[i]);  //更新为左边最大值
        	   rightmax=Math.max(rightmax, height[j]);  //更新为右边最大值
        	   if(leftmax<rightmax)  //如果左边最大值小于右边最大值，左边就为限制因素
        	   {
        		   max+=leftmax-height[i];   //接水量=左边最大值-当前格子值
        		   i++; //指针后移，计算下一个格子
        	   }
        	   else  //如果左边最大值大于等于右边最大值，右边就为限制因素
        	   {
        		   max+=rightmax-height[j];   //接水量=右边最大值-当前格子值
        		   j--;  //指针前移，计算前一个格子
        	   }
        	   
           }
              return max;
	    }
		
}