LeetCode-42-接雨水

目录

• 题目
• 自己思路
• 题解思路
• • 第一种:求每一列有多少雨水
  • 第二种：动态规划
  • 第三种：双指针
• 错误代码（样例通过318/320）
• 代码（第一种方法）
• 代码（动态规划）
• 代码（双指针）

题目

自己思路

1. 计算蓝色部分的面积…我一开始还以为计算重合面积。

2. 最左边不能存雨水，所以必须左右两个都存在才能存雨水。

3. 构想是建立rain[height.length][max]的数组，但是看题目这样有10^9的复杂度，估计不能AC，但是先写一下。
   

4. 果然暴力只能318/320，肯定有更好的解法，代码已经放在后面，感觉怎么都得投射到二维，可是二维的话就超过时间复杂度，润去题解。

题解思路

第一种:求每一列有多少雨水

1. 求每一列会有多少雨水，所以只用关注自己这列的柱子，往左走最高的柱子和往右走最高的柱子即可。
2. 具体积多少水，需要看两边柱子里较短的那边和自己这列的长度比较。（可知第一列和最后一列必定不会有柱子）
   3.显然可知，只有在较矮的柱子大于自己这列的高度时，才会有雨水积起，积的高度为二者之差。

第二种：动态规划

1. 第一种方法中，每到一个新的柱子，就需要对左右进行一次遍历查找最高，这样的话有很多重复遍历，可以用动态规划解决这个问题。

第三种：双指针

1. 首先初始化为left=0，right=height.length-1，left_max=right_max=0
   接雨水的性质，决定了当左右最高的柱子不一样高时，每列是以最短的那根柱子为基准的。
2. 如果从左往右遍历，那么left_max是可信的，因为已经遍历过了，而此时right_max是不可信的，因为右边柱子没有遍历完，并不确定它是否为右边最高的柱子。
3. 但如果此时的left_max

错误代码（样例通过318/320）

    public static int trap(int[] height) {//找到数组中最大值，将其作为高构成二维数组int max=0;for(int i=0;i<height.length;i++){max = Math.max(max,height[i]);}//建立二维数组 1记录柱子int[][] rain=new int[height.length][max];for(int i=0;i<height.length;i++){for(int j=0;j<max;j++){if(j<height[i]) rain[i][j]=1;}}//开始查找不为1的能否存储雨水int ans=0;for(int i=0;i<height.length;i++){for(int j=0;j<max;j++){if(rain[i][j]!=1){//往最左找能否找到柱子boolean flag=false;for(int k=i;k>=0;k--){if(rain[k][j]==1){flag=true;break;}}//往右找能否找到柱子boolean flag1=false;for(int k=i;k<height.length;k++){if(rain[k][j]==1){flag1=true;break;}}//都有柱子则可以存雨水 否则不能存if(flag&&flag1) ans++;}}}return ans;}

代码（第一种方法）

    public static int trap(int[] height) {//第一列和最后一列肯定没水 不用考虑int ans=0;for(int i=1;i<height.length-1;i++){//找左边最高的柱子int left=-1;for(int j=i-1;j>=0;j--) left = Math.max(left,height[j]);int right=-1;for(int j=i+1;j<height.length;j++) right = Math.max(right,height[j]);//找出其中较矮的int ai = Math.min(left,right);//这个较矮的和本身比较 记住把最高的墙放入考虑//如果较矮的大于本身列 则可以存相差列的水if(ai>height[i]) ans+=(ai-height[i]);//如果小于等于本身列 就没水了}return ans;}

代码（动态规划）

    public int trap(int[] height) {//建立往左最高的柱子（不能包括自身）int[] left_max = new int[height.length];int[] right_max = new int[height.length];//开始赋值for(int i=0;i<height.length-1;i++){if(i==0) left_max[i]=0;else left_max[i] = Math.max(left_max[i-1],height[i-1]);}for(int i=height.length-1;i>0;i--){if(i==height.length-1) right_max[i]=0;else right_max[i] = Math.max(right_max[i+1],height[i+1]);}//第一列和最后一列肯定没水 不用考虑int ans=0;for(int i=1;i<height.length-1;i++){//找出其中较矮的int ai = Math.min(left_max[i],right_max[i]);//这个较矮的和本身比较 记住把最高的墙放入考虑//如果较矮的大于本身列 则可以存相差列的水if(ai>height[i]) ans+=(ai-height[i]);//如果小于等于本身列 就没水了}return ans;}

代码（双指针）

    public int trap(int[] height) {int left=0;int right=height.length-1;int left_max=0;int right_max=0;int ans=0;while(left<=right){if(left_max<=right_max){ //此时只用关注left即可//此时两者相比矮的一定是left_maxif(left_max>height[left]) ans+=(left_max-height[left]);//更新left_max 因为接下来就进入下一个循环 所以left不用减一left_max = Math.max(left_max,height[left]);left++;}else{//此时两者相比矮的一定是right_maxif(right_max>height[right]) ans+=(right_max-height[right]);right_max = Math.max(right_max,height[right]);right--;}}return ans;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！