友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
849. 到最近的人的最大距离
给你一个数组 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 * 104 -
seats[i]为0或1 -
至少有一个 空座位
-
至少有一个 座位上有人
思路分析
我的思路：从两边算各自距离有人座位的距离，再求最小值。
更优越的解法是：一次遍历，使用双指针记录上一个有人座位的位置和当前有人座位位置距离除以 2。另外，考虑一下距离两端的情况即可。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-05 21:37:27
*/
public int maxDistToClosest(int[] seats) {
int n = seats.length;
int[] right = new int[n];
Arrays.fill(right, -1);
int[] left = new int[n];
Arrays.fill(left, -1);
int index = -1;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) {
right[i] = 0;
if (index < 0) {
index = i;
} else {
index = n;
}
continue;
}
if (i > 0 && right[i - 1] >= 0) {
right[i] = right[i - 1] + 1;
}
}
// 只有一个人
if (index < n) {
return Math.max(index, n - index - 1);
}
for (int i = n - 1; i >= 0; i--) {
if (seats[i] == 1) {
left[i] = 0;
continue;
}
if (i < n - 1 && 0 <= left[i + 1]) {
left[i] = left[i + 1] + 1;
}
}
int result = 0;
for (int i = 0; i < n; i++) {
if (right[i] >= 0 && left[i] >= 0) {
result = Math.max(result, Math.min(right[i], left[i]));
} else {
result = Math.max(result, Math.max(right[i], left[i]));
}
}
return result;
}
参考资料
-
849. 到最近的人的最大距离 - 官方题解 — 官方题解是一坨💩，还不如 Java 一次遍历 好理解