Medium

题目描述

Alice 管理一家公司，并租用了一栋建筑物的一些楼层作为办公空间。Alice 决定将其中一些楼层作为特殊楼层，仅用于放松。

给你两个整数 bottom 和 top，表示 Alice 租用了从 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. 排序处理：首先对特殊楼层数组进行排序，这样可以按顺序处理相邻的特殊楼层。

  2. 计算间隔：对于排序后的特殊楼层数组，相邻两个特殊楼层 special[i-1] 和 special[i] 之间的连续普通楼层数为 special[i] - special[i-1] - 1。

  3. 边界处理：需要特别考虑两种边界情况：

    • 第一个特殊楼层之前的楼层：从 bottom 到第一个特殊楼层之间的连续楼层数为 special[0] - bottom
    • 最后一个特殊楼层之后的楼层：从最后一个特殊楼层到 top 之间的连续楼层数为 top - special[n-1]

  4. 取最大值：在所有可能的连续楼层段中找到最大值。

时间复杂度主要来自排序操作，空间复杂度为常数级别（如果不考虑排序的额外空间）。

代码实现

class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        sort(special.begin(), special.end());
        int maxFloors = 0;
        int n = special.size();
        
        // 检查第一个特殊楼层之前的楼层
        maxFloors = max(maxFloors, special[0] - bottom);
        
        // 检查相邻特殊楼层之间的间隔
        for (int i = 1; i < n; i++) {
            maxFloors = max(maxFloors, special[i] - special[i-1] - 1);
        }
        
        // 检查最后一个特殊楼层之后的楼层
        maxFloors = max(maxFloors, top - special[n-1]);
        
        return maxFloors;
    }
};

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()
        max_floors = 0
        n = len(special)
        
        # 检查第一个特殊楼层之前的楼层
        max_floors = max(max_floors, special[0] - bottom)
        
        # 检查相邻特殊楼层之间的间隔
        for i in range(1, n):
            max_floors = max(max_floors, special[i] - special[i-1] - 1)
        
        # 检查最后一个特殊楼层之后的楼层
        max_floors = max(max_floors, top - special[n-1])
        
        return max_floors

public class Solution {
    public int MaxConsecutive(int bottom, int top, int[] special) {
        Array.Sort(special);
        int maxFloors = 0;
        int n = special.Length;
        
        // 检查第一个特殊楼层之前的楼层
        maxFloors = Math.Max(maxFloors, special[0] - bottom);
        
        // 检查相邻特殊楼层之间的间隔
        for (int i = 1; i < n; i++) {
            maxFloors = Math.Max(maxFloors, special[i] - special[i-1] - 1);
        }
        
        // 检查最后一个特殊楼层之后的楼层
        maxFloors = Math.Max(maxFloors, top - special[n-1]);
        
        return maxFloors;
    }
}

var maxConsecutive = function(bottom, top, special) {
    special.sort((a, b) => a - b);
    let maxFloors = 0;
    const n = special.length;
    
    // 检查第一个特殊楼层之前的楼层
    maxFloors = Math.max(maxFloors, special[0] - bottom);
    
    // 检查相邻特殊楼层之间的间隔
    for (let i = 1; i < n; i++) {
        maxFloors = Math.max(maxFloors, special[i] - special[i-1] - 1);
    }
    
    // 检查最后一个特殊楼层之后的楼层
    maxFloors = Math.max(maxFloors, top - special[n-1]);
    
    return maxFloors;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要开销来自排序操作，其中 n 是特殊楼层的数量
空间复杂度O(1)只使用常数额外空间（不考虑排序的空间开销）

相关题目