849. 到最近的人的最大距离
题目描述
输入数组 seats 表示一排座位，下标从 0 开始。seats[i] = 1 表示第 i 个座位有人，seats[i] = 0 表示空着。保证至少有一个空座位，也至少有一个人。
亚历克斯要挑一个空座位坐下。座位 i 和 j 之间的距离是 |i - j|。他希望自己与离他最近的那个人之间的距离尽可能大。
返回这个距离可能达到的最大值。
示例 1
输入：seats = [1,0,0,0,1,0,1] 输出：2
解释：坐在下标 2，左右最近的人都相距 2；其他空位最近距离只有 1。
示例 2
输入：seats = [1,0,0,0] 输出：3
解释：坐在最后一个座位，离下标 0 的人距离为 3。
示例 3
输入：seats = [0,1] 输出：1
解释：唯一的空位在下标 0，与下标 1 的人距离为 1。
数据范围
2 <= seats.length <= 2 * 10^4seats[i]为0或1。- 至少有一个空座位。
- 至少有一个座位有人。
解题思路
答案只可能来自三类空位段：开头的一段（坐在最左端，距离 = 第一个人的下标）、结尾的一段（坐在最右端，距离 = n-1-最后一个人的下标）、两个人之间的一段（坐在正中间，距离 = (i-prev)//2）。一次扫描，记录上一个有人的位置 prev，每遇到一个人就结算它左边那段空位。
为什么正确
扫描到下标 i 时，best 等于 seats[0..i] 中开头段和所有夹在两人之间的空段能给出的最大距离；prev 是 i 之前最后一个人的位置。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
两端的空段不能除以 2：靠墙的那一侧没有人，应该直接坐到最边上；忘了扫描结束后结算结尾段，会错过 [1,0,0,0] 这类答案。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
n = len(seats)
prev = -1
best = 0
for i in range(n):
if seats[i] == 1:
if prev == -1:
best = i
else:
best = max(best, (i - prev) // 2)
prev = i
return max(best, n - 1 - prev)class Solution {
public int maxDistToClosest(int[] seats) {
int n = seats.length;
int prev = -1;
int best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) {
if (prev == -1) {
best = i;
} else {
best = Math.max(best, (i - prev) / 2);
}
prev = i;
}
}
return Math.max(best, n - 1 - prev);
}
}class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int n = seats.size();
int prev = -1;
int best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) {
if (prev == -1) {
best = i;
} else {
best = max(best, (i - prev) / 2);
}
prev = i;
}
}
return max(best, n - 1 - prev);
}
};func maxDistToClosest(seats []int) int {
n := len(seats)
prev := -1
best := 0
for i := 0; i < n; i++ {
if seats[i] == 1 {
if prev == -1 {
best = i
} else {
best = max(best, (i-prev)/2)
}
prev = i
}
}
return max(best, n-1-prev)
}var maxDistToClosest = function(seats) {
const n = seats.length;
let prev = -1;
let best = 0;
for (let i = 0; i < n; i++) {
if (seats[i] === 1) {
if (prev === -1) {
best = i;
} else {
best = Math.max(best, Math.floor((i - prev) / 2));
}
prev = i;
}
}
return Math.max(best, n - 1 - prev);
};function maxDistToClosest(seats: number[]): number {
const n = seats.length;
let prev = -1;
let best = 0;
for (let i = 0; i < n; i++) {
if (seats[i] === 1) {
if (prev === -1) {
best = i;
} else {
best = Math.max(best, Math.floor((i - prev) / 2));
}
prev = i;
}
}
return Math.max(best, n - 1 - prev);
}