最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇14_接雨水算法求解

XAMPP相关 admin 480浏览 0评论

来源:LeetCode

难度:困难

描述:

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

示例1:

drf40

示例2:

drf040

分析:要想接雨水,就必须有“坑”,要想有坑,那么这个位置的高度必须小于左边最大的高度和右边最大的高度,这里左右最大的高度可以不相邻,同时,有坑之后能接多少雨水还得看高度差,根据木桶蓄水原理,一个木桶能蓄多少水取决于最短的那块木板,同理,坑里能接多少水取决于左右最大高度中较小的那个高度与本位置高度之差,以下是一些解法

 

解题

方法一:按行求解法

思路:由上分析可知,咱们只要把数组中的坑的数量及大小计算出来就行,那么咱们可以一行一行找,把每行中的坑找到后累计数量即可,如下图

第一行坑的数量:2

drf0040

第二行坑的数量:4

drf00040

第三行无坑

drf000040

所以总坑数为6

 

代码:

 1public static int trap(int[] height) {
 2    if (height == null || height.length < 3) {
 3        return 0;
 4    }
 5    //求数组中最大行高
 6    int max = 0;
 7    for (int value : height) {
 8        max = Math.max(max, value);
 9    }
10    int sum = 0;
11    //一行一行求解
12    for (int i = 1; i <= max; i++) {
13        //标识是否找到第一个非0值 找到后才能形成坑
14        boolean start = false;
15        int temp = 0;
16        for (int value : height) {
17            //坑的数量
18            if (start && value < i) {
19                temp++;
20            }
21            //找到一个大于i,把坑的数量加上即是蓄水量
22            if (value >= i) {
23                start = true;
24                sum += temp;
25                temp = 0;
26            }
27        }
28    }
29    return sum;
30}

时间复杂度:O(m*n) 其中m是数组中最大的数

空间复杂度:O(1)

 

该方法在最大数(行高)较小时性能可观,太大的时候存在大量遍历,性能直线下降,下面咱看另外几种解法

 

方法二:按列求解法(动态规划)

思路:由分析可知,一个位置能蓄水多少需要和它右边的最大值及左边的最大值中较小的那个进行比较,差值就是蓄水量,那么咱们用两个数组leftmax和rightmax分别存储每个位置左边的最大值和右边的最大值,之后咱们一个将每个位置的蓄水量计算出来累加即可

代码:

 1public static int trap4(int[] height) {
 2        if (height == null || height.length < 3) {
 3            return 0;
 4        }
 5        int sum = 0;
 6        //leftMax 每位装 该位置左边的最大值
 7        int[] leftMax = new int[height.length];
 8        leftMax[0] = height[0];
 9        //rightMax 每位装 该位置右边的最大值
10        int[] rightMax = new int[height.length];
11        rightMax[height.length - 1] = height[height.length - 1];
12        //第一位已经填充 那么从1开始遍历填充leftMax数组
13        for (int i = 1; i < height.length; i++) {
14            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
15        }
16        //最后一位已经填充 那么从倒数第二位开始填充rightMax数组
17        for (int i = height.length - 2; i >= 0; i--) {
18            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
19        }
20        for (int i = 0; i < height.length; i++) {
21            //这里如果本位置元素最大 那么leftMax[i]和rightMax[i]都会与本位置相等 即不形成坑
22            //若本位置最小  则形成坑
23            //且该位置能装的水 = 左右两边较小的那个和 本位置的差值
24            sum += Math.min(leftMax[i], rightMax[i]) - height[i];
25        }
26        return sum;
27    }

时间复杂度:O(n)

空间复杂度:O(n)

 

方法三:双指针法

思路:思路和方法二一致,只是此处用两个指针代表左边的最大值和右边的最大值,且指针由两边向中间聚拢,不断更新左右最大值,并将每个位置蓄水量计算累加即可

 

代码:

 1public static int trap2(int[] height) {
 2    if (height == null || height.length < 3) {
 3        return 0;
 4    }
 5    int sum = 0;
 6    int leftMax = height[0];
 7    int rightMax = height[height.length - 1];
 8    int left = 0;
 9    int right = height.length - 1;
10    while (left < right) {
11        //更新右边最大值
12        rightMax = Math.max(rightMax, height[right]);
13        //更新右边最大值
14        leftMax = Math.max(leftMax, height[left]);
15        //右边的数大
16        if (height[right] > height[left]) {
17            //根据木桶装水原理,装水量取决于最短的木板
18            // 则 leftMax i rightMax 三柱之间装水量为
19            // leftMax 和rightMax 之间较短的那个和 i的差值
20            sum += Math.min(rightMax, leftMax) - height[left];
21            //右边的值大,保持不动,左边的前进
22            left++;
23        } else {
24            sum += Math.min(rightMax, leftMax) - height[right];
25            //左边的值大,保持不动,右边的后退
26            right--;
27        }
28    }
29    return sum;
30}

时间复杂度:O(n)

空间复杂度:O(1)

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇14_接雨水算法求解

您必须 登录 才能发表评论!