力扣周赛293--第二题

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 <= special.length <= 105
• 1 <= bottom <= special[i] <= top <= 109
• special 中的所有值 互不相同

思路

这题相当于在bottom到top的范围内，被special的数分割了，我们需要找到分割后最长的一段

步骤：

1. 为了保证数据的顺序进行，对special进行排序
2. 遍历special对bottom~top进行分割，当bottom<=special[i]时，
   连续楼层数为special[i]-bottom，与之前的最大连续层数对比，得到当前的最大连续层数，
   同时更新bottom = special[i] + 1
3. 遍历完，还有最后一段的连续层数top - special[special.length - 1]
4. 至此，不包含特殊层的最大的连续层数就出来了

代码

java：

class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int max = 0;
        for (int j : special) {
            if (bottom <= j) {
                max = Math.max(max, j - bottom);
                bottom = j + 1;
            }
        }
        max = Math.max(max, top - special[special.length - 1]);
        return max;
    }
}