题解 | #接雨水问题#
接雨水问题
http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
描述
- 给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个柱子高度图,计算按此排列的柱子,下雨之后能接多少雨水。
- 示例1
输入:[3,1,2,5,2,4]
返回值:5
说明:数组 [3,1,2,5,2,4] 表示柱子高度图,在这种情况下,可以接 5个单位的雨水,蓝色的为雨水 - 示例2
输入:[4,5,1,3,2]
返回值:2
备注:
方法一
思路
- 暴力遍历
- 可以对每一个位置计算其容水量,这里将每一个下标类比为坑。譬如说,我需要对下标为index的位置计算能够装多少水,我需要找这个坑的左右边界,而它的左右边界实际上就是其左右数据的最大值maxleft以及maxright,,当容量为负数时,记为0,不装水。
- 所以可以遍历数组,计算从1~n的所有坑的容量,总和即为所接雨水的总容量。
- 代码如下:
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { // 返回0 if(arr == null || arr.length < 3){ return 0; } // 接水数 long count = 0; int len = arr.length; int nextLen = len - 1; for (int i = 1;i < nextLen;++i){ int maxLeft = 0; int maxRight = 0; // 求左侧最大值 for (int j = 0;j < i;++j){ maxLeft = Math.max(arr[j],maxLeft); } // 求右侧最大值 for(int m = i + 1;m < len;++m){ maxRight = Math.max(maxRight,arr[m]); } // 当前坑的接水数 int height = Math.min(maxRight,maxLeft) - arr[i]; count += Math.max(0,height) ; } return count; } }
- 时间复杂度:,双重循环;
- 空间复杂度:,常数级空间复杂度。
方法二
思路
- 两次遍历,双指针
- 接雨水通俗点说就是找坑,坑的数量以及总容量即为所接雨水的数量,对于递增序列以及递减序列一定是没有坑的,也就是这种序列是接不到雨水的。
- 那么有坑的条件是什么呢?
- 假设某坑的边界是(i,j),那么坑中的数据必然是满足如下条件的:
- 对于边界则存在如下三种情况:
1.
2.
3. - 故可以分两次遍历计算坑的总容量,第一次从左往右遍历,找出满足情况2的坑容量,第二次从右往左遍历找出满足情况1和3的坑容量,两次结果相加即为坑的总容量。
- 参考下图示例:
- 代码如下:
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { if(arr == null || arr.length < 3){ return 0; } int p = 0; int q = 1; int len = arr.length; long count = 0; // 递增序列不考虑 while(q < len && arr[p] <= arr[q]){ ++p; ++q; } long temp = 0; // 从左往右遍历 while(q < len){ // 记录存储雨水量 if (arr[p] > arr[q]){ temp = temp + arr[p] - arr[q]; ++q; }else{ // 避免重复计算,所以这里不记录,在倒序处记录 if (arr[p] == arr[q]){ temp = 0; } p = q; ++q; count += temp; temp = 0; } } p = len - 1; q = len - 2; // 递减序列不考虑 while(q >= 0 && arr[q] >= arr[p]){ --q; --p; } temp = 0; // 从右往左遍历 while(q >= 0){ if (arr[p] > arr[q]){ temp = temp + arr[p] - arr[q]; --q; }else{ p = q; --q; count += temp; temp = 0; } } return count; } }
- 时间复杂度:,两次一重循环;
- 空间复杂度:,常数级空间复杂度。