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

标签: 数组 排序

难度: Medium

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。

给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示  Alice 指定用于放松的特殊楼层。

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

示例 1：

输入：bottom = 2, top = 9, special = [4,6]
输出：3
解释：下面列出的是不含特殊楼层的连续楼层范围：
- (2, 3) ，楼层数为 2 。
- (5, 5) ，楼层数为 1 。
- (7, 9) ，楼层数为 3 。
因此，返回最大连续楼层数 3 。

示例 2：

输入：bottom = 6, top = 8, special = [7,6,8]
输出：0
解释：每层楼都被规划为特殊楼层，所以返回 0 。

提示

  • 1 <= special.length <= 105
  • 1 <= bottom <= special[i] <= top <= 109
  • special 中的所有值 互不相同

Submission

运行时间: 151 ms

内存: 29.2 MB

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        start=bottom
        special.sort()
        ml=0
        for i in special:
            lin=i-start
            start=i+1
            if lin>ml:
                ml=lin
        if top>i and top-i>ml:
            ml=top-i
        return ml

Explain

题解的思路是先对特殊楼层进行排序，然后遍历特殊楼层数组，计算相邻特殊楼层之间的楼层数（即连续的非特殊楼层数量）。这样可以找出最大的连续非特殊楼层数。同时，还需要考虑特殊楼层数组的第一个元素之前以及最后一个元素之后的连续非特殊楼层数。

时间复杂度: O(nlogn)

空间复杂度: O(1)

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        start = bottom  # 初始化连续非特殊楼层的起始楼层
        special.sort()  # 对特殊楼层进行排序
        ml = 0  # 最大连续非特殊楼层数
        for i in special:
            lin = i - start  # 计算当前连续非特殊楼层数
            start = i + 1  # 更新下一段连续非特殊楼层的起始楼层
            if lin > ml:
                ml = lin  # 更新最大连续非特殊楼层数
        if top > i and top - i > ml:
            ml = top - i  # 检查最后一个特殊楼层之后的连续非特殊楼层数
        return ml

Explore

如果数组special为空，那么在算法中不会进入for循环，因为没有特殊楼层需要迭代。因此，需要在for循环后判断是否有特殊楼层处理过。如果special为空，直接计算bottom到top之间的楼层数作为连续楼层数。这是通过top - bottom + 1来计算的，确实可以正确计算从bottom到top的范围作为连续楼层数。

初始化连续非特殊楼层的起始楼层为bottom是必要的，因为算法需要从building的最底层开始计算连续的非特殊楼层。排序后的第一个特殊楼层之前的所有楼层都是连续的非特殊楼层，如果不从bottom开始，那么这部分楼层将无法被正确计算。

当特殊楼层的元素恰好是bottom时，算法通过设置开始点start为bottom，并在遇到第一个特殊楼层时立即更新start为该特殊楼层的下一层，从而跳过计算该特殊楼层作为连续非特殊楼层的一部分。而当特殊楼层元素是top时，由于计算其他特殊楼层之间的间隙时，起始点start始终设置为当前特殊楼层的下一层，这确保了即使top是特殊楼层，它也不会被错误地计入连续非特殊楼层数。

最后一个特殊楼层之后的连续楼层数是通过计算top（楼层总的最高层）与最后一个特殊楼层之间的差来获得的。在代码中，使用top > i来确保top楼层高于最后一个特殊楼层i。而top - i > ml是用来检查最后一个特殊楼层之后的连续楼层数是否大于之前计算得到的最大连续楼层数ml，如果是，则更新ml为这个新值。这样可以确保找到整个楼层范围内的最大连续非特殊楼层数。