【LetMeFly】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 <= 1051 <= bottom <= special[i] <= top <= 109special 中的所有值 互不相同
解题方法：排序
对“特殊楼层”从小到大排序，统计如下三者的最大值即为答案：
- $special[0] - bottom$
- $special[i] - special[i - 1] - 1$，其中$1\leq i\lt len(special)$
- $top - special[len(special) - 1]$
- 时间复杂度$O(n\log n)$，其中$n=len(special)$
- 空间复杂度$O(\log n)$
AC代码
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| '''
Author: LetMeFly
Date: 2025-01-06 20:36:27
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-06 20:38:18
'''
from typing import List
class Solution:
def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
special.sort()
ans = max(special[0] - bottom, top - special[-1])
for i in range(1, len(special)):
ans = max(ans, special[i] - special[i - 1] - 1)
return ans
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int maxConsecutive(int bottom, int top, vector<int>& special) {
sort(special.begin(), special.end());
int ans = top - special.back();
bottom--;
for (int t : special) {
ans = max(ans, t - bottom - 1);
bottom = t;
}
return ans;
}
};
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
import java.util.Arrays;
class Solution {
public int maxConsecutive(int bottom, int top, int[] special) {
Arrays.sort(special);
int ans = Math.max(special[0] - bottom, top - special[special.length - 1]);
for (int i = 1; i < special.length; i++) {
ans = Math.max(ans, special[i] - special[i - 1] - 1);
}
return ans;
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
package main
import "sort"
func max_MCFWSF(a, b int) int {
if a > b {
return a
}
return b
}
func maxConsecutive(bottom int, top int, special []int) (ans int) {
sort.Ints(special)
ans = max_MCFWSF(special[0] - bottom, top - special[len(special) - 1])
for i := 1; i < len(special); i++ {
ans = max_MCFWSF(ans, special[i] - special[i - 1] - 1)
}
return
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/144972086