How does sorting special floors help in finding maximum consecutive floors?

Sorting ensures that we can calculate gaps between consecutive special floors accurately, which directly gives consecutive non-special floors.

What if all floors are special?

If all floors between bottom and top are special, there are no consecutive non-special floors, so the result is 0.

How is the gap between special floors calculated?

For two sorted special floors x and y, the number of consecutive non-special floors is x - y - 1.

Does the bottom or top floor affect the result?

Yes, gaps before the first special floor and after the last special floor must be considered to find the true maximum.

What pattern does this problem follow in arrays?

This is an array plus sorting pattern problem where sorting enables efficient consecutive gap computation between special elements.

#2274

Medium

auto_awesome数组·排序

LeetCode 题解工作台

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

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为特殊楼层，仅用于放松。给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top （含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special…

数组排序

题目描述

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⁵
1 <= bottom <= special[i] <= top <= 10⁹
special 中的所有值 互不相同

lightbulb

解题思路

方法一：排序

我们可以将特殊楼层按照升序排序，然后计算相邻两个特殊楼层之间的楼层数，最后再计算第一个特殊楼层和 $\textit{bottom}$ 之间的楼层数，以及最后一个特殊楼层和 $\textit{top}$ 之间的楼层数，取这些楼层数的最大值即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $\textit{special}$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()
        ans = max(special[0] - bottom, top - special[-1])
        for x, y in pairwise(special):
            ans = max(ans, y - x - 1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting special floors is critical for correct gap calculation.
question_mark
Checking all edge cases including first and last floor gaps is expected.
question_mark
Tracking maximum while iterating shows understanding of array manipulation patterns.

warning

常见陷阱

外企场景

error
Forgetting to sort special floors before computing gaps leads to incorrect results.
error
Ignoring the gap before the first special floor or after the last special floor can miss the true maximum.
error
Assuming consecutive floors are only between special floors and not including bottom and top boundaries.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return both the maximum consecutive floors and the starting floor of that sequence.
arrow_right_alt
Count the total number of consecutive sequences longer than a given threshold.
arrow_right_alt
Allow dynamic insertion of special floors and compute the maximum consecutive floors after each insertion.

help

常见问题

外企场景

继续练习

#2273 移除字母异位词后的结果数组 #2271 毯子覆盖的最多白色砖块数 #2279 装满石头的背包的最大数量