侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【排序, 分类讨论】不含特殊楼层的最大连续楼层数

GabrielxD
2022-05-15 / 0 评论 / 0 点赞 / 35 阅读 / 454 字 / 正在检测是否收录...

题目

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


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

给你两个整数 bottomtop ,表示 Alice 租用了从 bottomtop(含 bottomtop 在内)的所有楼层。另给你一个整数数组 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 中的所有值 互不相同

解题

方法一:排序 分类讨论

思路

special 排序后可得:

  • 从最低层到第一个特殊楼层之间连续普通楼层数为 special[0] - bottom
  • 从最后一个特殊楼层到最高层之间连续普通楼层数为 top - special[len - 1]
  • 其他连续普通楼层数为 special[i + 1] - special[i] - 1

从这三种情况中选一个最大的。

代码

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

评论区