摘要: 排序的应用一例

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天轻松一些，来看一个常规的 leetcode 题，平台给出的难度等级为中等，不过算法来看应该算是简单。只要能分析出通过排序可以解决问题，注意一下边界条件即可。

题目

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

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
2
3

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

题解

算法: 排序

将 bottom - 1 和 top + 1 插入 special，记特殊楼层集合 special 的长度为 n，将 special 排序。

排序后，相邻的元素 special[i], special[i+1] 就是相邻的两个特殊楼层，special[i+1] - special[i] - 1 就是这两个相邻特殊楼层之间夹着的连续楼层数，其中 i=0,1,...,n-2。若区间范围在 [bottom, top] 之内，则更新答案。

取其中最大的即可。排序的时间复杂度为 $O(N\log N)$，排序后统计答案的过程为 $O(N)$，总时间复杂度为 $O(N\log N)$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.extend([bottom - 1, top + 1])
        special.sort()
        n = len(special)
        ans = 0
        for i in range(n - 1):
            if special[i] < bottom - 1:
                continue
            if special[i + 1] > top + 1:
                continue
            ans = max(ans, special[i + 1] - special[i] - 1)
        return ans