[LeetCode] 每日一题 2274. 不含特殊楼层的最大连续楼层数

题目链接

https://leetcode.cn/problems/maximum-consecutive-floors-without-special-floors/

题目描述

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 <= 10^5

• 1 <= bottom <= special[i] <= top <= 10^9

• special 中的所有值 互不相同

题解

解题思路

这道题要求我们计算最大连续的非特殊楼层数量。可以通过以下步骤解决问题：

1. 排序特殊楼层数组：将 special 按升序排列

2. 考虑边界情况：

   • 起始的非特殊楼层数量为 special[0] - bottom

   • 结束的非特殊楼层数量为 top - special[special.length - 1]

3. 计算中间段的非特殊楼层：

   • 相邻两个特殊楼层 special[i - 1] 和 special[i] 之间的非特殊楼层数量为 special[i] - special[i - 1] - 1

4. 更新最大值：

   • 在遍历时逐步更新最大连续非特殊楼层数

通过这一步步的分析，最终可以得到结果

代码实现

class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        // 排序特殊楼层数组
        Arrays.sort(special);
        int ans = 0;
        
        // 考虑起始的非特殊楼层数量
        ans = Math.max(ans, special[0] - bottom);
        
        // 遍历相邻的特殊楼层，计算非特殊楼层数量
        for (int i = 1; i < special.length; ++i) {
            ans = Math.max(ans, special[i] - special[i - 1] - 1);
        }
        
        // 考虑结束的非特殊楼层数量
        ans = Math.max(ans, top - special[special.length - 1]);
        
        return ans;
    }
}

复杂度分析

1. 时间复杂度：

   • 排序特殊楼层数组需要 O(n log n)，其中 n 是数组 special 的长度

   • 遍历特殊楼层数组一次，计算最大值需要 O(n)

   • 总时间复杂度为 O(n log n)

2. 空间复杂度：

   • 排序操作通常需要额外的空间，但 Java 的 Arrays.sort 对基本数据类型使用原地排序，因此额外空间复杂度为 O(1)

总结

本题通过排序和线性扫描有效解决了最大连续非特殊楼层的问题，整体思路清晰且代码简洁。关键点在于考虑边界情况和排序后利用相邻楼层差值来计算答案

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。