leetcode
leetcode 1951 ~ 2000
不含特殊楼层的最大连续楼层数

不含特殊楼层的最大连续楼层数

难度:

标签:

题目描述

代码结果

运行时间: 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为空,那么在算法中不会进入for循环,因为没有特殊楼层需要迭代。因此,需要在for循环后判断是否有特殊楼层处理过。如果special为空,直接计算bottom到top之间的楼层数作为连续楼层数。这是通过top - bottom + 1来计算的,确实可以正确计算从bottom到top的范围作为连续楼层数。
🦆
在对special数组进行排序后,为什么需要初始化连续非特殊楼层的起始楼层为bottom?
初始化连续非特殊楼层的起始楼层为bottom是必要的,因为算法需要从building的最底层开始计算连续的非特殊楼层。排序后的第一个特殊楼层之前的所有楼层都是连续的非特殊楼层,如果不从bottom开始,那么这部分楼层将无法被正确计算。
🦆
当特殊楼层的元素恰好是bottom或top时,算法如何确保不会计算错误的连续非特殊楼层数?
当特殊楼层的元素恰好是bottom时,算法通过设置开始点start为bottom,并在遇到第一个特殊楼层时立即更新start为该特殊楼层的下一层,从而跳过计算该特殊楼层作为连续非特殊楼层的一部分。而当特殊楼层元素是top时,由于计算其他特殊楼层之间的间隙时,起始点start始终设置为当前特殊楼层的下一层,这确保了即使top是特殊楼层,它也不会被错误地计入连续非特殊楼层数。
🦆
算法中最后一个特殊楼层之后的连续楼层数是如何计算的?为什么使用条件top > i和top - i > ml?
最后一个特殊楼层之后的连续楼层数是通过计算top(楼层总的最高层)与最后一个特殊楼层之间的差来获得的。在代码中,使用top > i来确保top楼层高于最后一个特殊楼层i。而top - i > ml是用来检查最后一个特殊楼层之后的连续楼层数是否大于之前计算得到的最大连续楼层数ml,如果是,则更新ml为这个新值。这样可以确保找到整个楼层范围内的最大连续非特殊楼层数。

相关问题