到最近的人的最大距离
难度:
标签:
题目描述
给你一个数组 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
- 至少有一个 空座位
- 至少有一个 座位上有人
代码结果
运行时间: 32 ms, 内存: 17.7 MB
/*
* 思路:
* 使用Java Stream API解决这个问题。
* 将座位数组转换为索引流,记录每个空座位到最近的人的距离。
* 分别考虑座位最左端、最右端和中间位置的情况。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxDistToClosest(int[] seats) {
int n = seats.length;
int lastPerson = IntStream.range(0, n).filter(i -> seats[i] == 1).findFirst().orElse(-1);
int maxDist = IntStream.range(0, n)
.filter(i -> seats[i] == 0)
.map(i -> i < lastPerson ? lastPerson - i :
IntStream.range(lastPerson + 1, n).filter(j -> seats[j] == 1).map(j -> Math.min(j - i, i - lastPerson)).min().orElse(n - 1 - i))
.max()
.orElse(0);
return maxDist;
}
}
解释
方法:
该题解采用的思路主要是找到所有已经有人坐的座位的下标,然后计算两者之间的最大空位数。首先,遍历整个座位数组,将所有有人的座位的下标存入列表pos中。如果pos中只有一个元素,即只有一个座位有人,直接计算该座位到数组两端的距离中的最大值。如果有多个有人的座位,计算相邻两个有人座位之间的距离,存入dist数组中。对于dist数组中的每个元素值,实际上代表了从一个有人的座位到下一个有人的座位之间的空座位数。这样,最远的可能距离将是dist中的最大值除以2(因为坐在两人正中间时距离最远)。最后,比较三种情况下的最大距离:1) 最左边的有人座位到数组开始的距离,2) 最右边的有人座位到数组结束的距离,3) dist数组中的最大值除以2。最终返回这三者之中的最大值。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在计算最大距离时,选择将相邻有人座位之间的最大距离除以2取整来表示?
▷🦆
在题解中,如果座位序列的两端都是空的,是如何处理这两端空座位的最大距离的?
▷🦆
题解中提到的特殊情况处理,即只有一个有人的座位,为什么直接返回该座位到两端的最大距离而不是考虑其它因素?
▷🦆
题解中的算法是否考虑了座位数组全为空的情况,即`seats`数组全为0,这种情况下该如何处理?
▷相关问题
考场就座
在考场里,一排有 N
个座位,分别编号为 0, 1, 2, ..., N-1
。
当学生进入考场后,他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位,他会坐在编号最小的座位上。(另外,如果考场里没有人,那么学生就坐在 0 号座位上。)
返回 ExamRoom(int N)
类,它有两个公开的函数:其中,函数 ExamRoom.seat()
会返回一个 int
(整型数据),代表学生坐的位置;函数 ExamRoom.leave(int p)
代表坐在座位 p
上的学生现在离开了考场。每次调用 ExamRoom.leave(p)
时都保证有学生坐在座位 p
上。
示例:
输入:["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]] 输出:[null,0,9,4,2,null,5] 解释: ExamRoom(10) -> null seat() -> 0,没有人在考场里,那么学生坐在 0 号座位上。 seat() -> 9,学生最后坐在 9 号座位上。 seat() -> 4,学生最后坐在 4 号座位上。 seat() -> 2,学生最后坐在 2 号座位上。 leave(4) -> null seat() -> 5,学生最后坐在 5 号座位上。
提示:
1 <= N <= 10^9
- 在所有的测试样例中
ExamRoom.seat()
和ExamRoom.leave()
最多被调用10^4
次。 - 保证在调用
ExamRoom.leave(p)
时有学生正坐在座位p
上。