不含特殊楼层的最大连续楼层数
难度:
标签:
题目描述
代码结果
运行时间: 151 ms, 内存: 29.2 MB
/*
思路:
1. 使用流的方式处理数组。
2. 计算 special 数组中连续非特殊楼层的最大数量。
*/
import java.util.Arrays;
public class MaxConsecutiveFloorsStream {
public static int maxConsecutive(int bottom, int top, int[] special) {
// 对特殊楼层进行排序
Arrays.sort(special);
// 使用流计算最大连续非特殊楼层数
return Math.max(Arrays.stream(special).reduce(
new int[]{bottom - 1, 0},
(acc, floor) -> new int[]{floor, Math.max(acc[1], floor - acc[0] - 1)},
(acc1, acc2) -> new int[]{acc2[0], Math.max(acc1[1], acc2[1])})[1],
top - special[special.length - 1]);
}
}
解释
方法:
题解的思路是先对特殊楼层进行排序,然后遍历特殊楼层数组,计算相邻特殊楼层之间的楼层数(即连续的非特殊楼层数量)。这样可以找出最大的连续非特殊楼层数。同时,还需要考虑特殊楼层数组的第一个元素之前以及最后一个元素之后的连续非特殊楼层数。
时间复杂度:
O(nlogn)
空间复杂度:
O(1)
代码细节讲解
🦆
如果数组special为空,算法将如何处理?从bottom到top的范围是否会被正确计算为连续楼层数?
▷🦆
在对special数组进行排序后,为什么需要初始化连续非特殊楼层的起始楼层为bottom?
▷🦆
当特殊楼层的元素恰好是bottom或top时,算法如何确保不会计算错误的连续非特殊楼层数?
▷🦆
算法中最后一个特殊楼层之后的连续楼层数是如何计算的?为什么使用条件top > i和top - i > ml?
▷