接雨水

刺骨的言语ヽ痛彻心扉 2022-01-26 16:27 118阅读 0赞

### 题目描述 ###

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。  
![在这里插入图片描述][20190529153652107.png]  
上面是由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

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

### 1、 暴力法 ###

/** *接雨水，暴力解法 * 对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。 * @param height * @return */
    public int trap(int[] height) { 
           if(height == null || height.length < 2) { 
           	return 0;
           }
           int leftMax=0, rightMax=0;
           int count=0;
           for(int i=1;i<height.length-1;i++) { 
           	leftMax=0;rightMax=0;
           	for(int j=0;j<i;j++) { 
           		leftMax = Math.max(leftMax, height[j]);
           	}
           	for(int j=height.length-1; j>i;j--) { 
           		rightMax = Math.max(rightMax, height[j]);
           	}
           	if(leftMax>0 && rightMax>0 && Math.min(leftMax, rightMax)>height[i]) { 
           		count+=(Math.min(leftMax, rightMax) - height[i]);
           	}
           }
           return count;
       }

### 2、空间换时间 ###

/** *接雨水 * 用空间换时间，记录下每个节点的左侧最大值，右侧最大值 * 对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。 * @param height * @return */
    public int trap(int[] height) { 
           if(height == null || height.length < 2) { 
           	return 0;
           }
           int[] leftMax = new int[height.length];
           for(int i=1;i<height.length;i++) { 
           	leftMax[i] = Math.max(leftMax[i-1], height[i-1]);
           }
           int[] rightMax = new int[height.length];
           for(int i=height.length-2;i>=0;i--) { 
           	rightMax[i] = Math.max(rightMax[i+1], height[i+1]);
           }
           
           int count=0;
           for(int i=1;i<height.length-1;i++) { 
           	if(Math.min(leftMax[i], rightMax[i])>height[i]) { 
           		count+=(Math.min(leftMax[i], rightMax[i])-height[i]);
           	}
           }
           return count;
       }

[20190529153652107.png]: /images/20220126/8c587826b7cc418e8448b3d2553412c9.png