How do you handle leading and trailing empty seats in Maximize Distance to Closest Person?

Treat leading or trailing zeros as special cases; the distance is the number of consecutive empty seats up to the nearest occupied seat.

Can this problem be solved in one pass with constant space?

Yes, by tracking current consecutive empty seats and updating the maximum distance during a single linear scan.

Why is the maximum distance often half the largest internal gap?

Because the optimal seat in the middle of a consecutive empty segment places Alex at equal distance from both neighboring occupied seats.

What if all seats are empty except one?

The maximum distance is the length of the longest gap from the single occupied seat, which will be at one of the edges.

Does the array-driven solution pattern apply to other seating optimization problems?

Yes, the same approach works for any linear seating arrangement where maximizing minimum distance is required.

#849

Medium

auto_awesome数组·driven

LeetCode 题解工作台

到最近的人的最大距离

给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上， seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。至少有一个空座位，且至少有一人已经坐在座位上。亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。…

数组

题目描述

给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。

至少有一个空座位，且至少有一人已经坐在座位上。

亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。

返回他到离他最近的人的最大距离。

示例 1：

输入：seats = [1,0,0,0,1,0,1]
输出：2
解释：
如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
因此，他到离他最近的人的最大距离是 2 。

示例 2：

输入：seats = [1,0,0,0]
输出：3
解释：
如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。
这是可能的最大距离，所以答案是 3 。

示例 3：

输入：seats = [0,1]
输出：1

提示：

2 <= seats.length <= 2 * 10⁴
seats[i] 为 0 或 1
至少有一个 空座位
至少有一个 座位上有人

lightbulb

解题思路

方法一：一次遍历

我们定义两个变量 $\textit{first}$ 和 $\textit{last}$ 分别表示第一个人和最后一个人的位置，用变量 $d$ 表示两个人之间的最大距离。

然后遍历数组 $\textit{seats}$ ，如果当前位置有人，如果此前 $\textit{last}$ 更新过，说明此前有人，此时更新 $d = \max(d, i - \textit{last})$ ；如果此前 $\textit{first}$ 没有更新过，说明此前没有人，此时更新 $\textit{first} = i$ 。接下来更新 $\textit{last} = i$ 。

最后返回 $\max(\textit{first}, n - \textit{last} - 1, d / 2)$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{seats}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        first = last = None
        d = 0
        for i, c in enumerate(seats):
            if c:
                if last is not None:
                    d = max(d, i - last)
                if first is None:
                    first = i
                last = i
        return max(first, len(seats) - last - 1, d // 2)

speed

复杂度分析

指标	值
时间	complexity is $O(N)$ because the array is traversed once to track empty gaps. Space complexity is $O(1)$ since only counters for distances are maintained without additional storage proportional to input size.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Asks about handling edge seats separately from middle segments.
question_mark
Questions why a simple mid-gap division works for consecutive empty seats.
question_mark
Explores if the solution can be done in one pass without extra arrays.

warning

常见陷阱

外企场景

error
Forgetting to account for empty seats at the beginning or end of the array.
error
Using integer division incorrectly when computing half-gaps inside the array.
error
Scanning multiple times instead of maintaining running counters, increasing time complexity unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if multiple people can be seated sequentially to maximize distance?
arrow_right_alt
Consider a circular row where the first and last seats are adjacent.
arrow_right_alt
Modify the array to include reserved seats that cannot be chosen and recalculate maximum distance.

help

常见问题

外企场景

继续练习

#848 字母移位 #850 矩形面积 II #851 喧闹和富有