leetcode
leetcode 751 ~ 800
到最近的人的最大距离

到最近的人的最大距离

难度:

标签:

题目描述

给你一个数组 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]01
  • 至少有一个 空座位
  • 至少有一个 座位上有人

代码结果

运行时间: 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取整来表示?
在计算最大距离时,将相邻有人座位之间的距离除以2是因为,如果希望找到离人最远的空座位,理想的位置是正好位于两个已坐人之间的中点。例如,如果有人的座位分别位于位置 0 和位置 10,那么位置 5(即中间位置)将是离两边人最远的位置。因此,除以2是为了找到这种中间位置,从而确保计算出的距离是从该空座位到最近的人的最大可能距离。
🦆
在题解中,如果座位序列的两端都是空的,是如何处理这两端空座位的最大距离的?
在题解中,如果座位序列的两端都是空的,则直接计算从序列两端到最近的有人座位的距离。这些距离是通过计算最左边有人的座位的索引(即列表中的第一个元素)和最右边有人的座位的索引(即列表中的最后一个元素)来得到的。最左边的距离是第一个有人的座位的索引值,而最右边的距离是座位总数减去最后一个有人的座位的索引再减1。这两个值分别代表了从数组开始和结束到最近有人座位的直接距离。
🦆
题解中提到的特殊情况处理,即只有一个有人的座位,为什么直接返回该座位到两端的最大距离而不是考虑其它因素?
在只有一个有人的座位的情况下,该座位自然成为了分隔两段空座位的界限。此时,离这个有人座位最远的空座位必然位于数组的两端,因此,计算该座位到数组两端的距离,并取这两个距离中的最大值即可。这种处理方式是因为在只有一个有人的座位时,其他所有的座位都是空的,且这些空座位距离有人座位的远近就是直接的物理距离。
🦆
题解中的算法是否考虑了座位数组全为空的情况,即`seats`数组全为0,这种情况下该如何处理?
题解中的算法未直接提及当座位数组全为空(即`seats`数组全为0)的情况。理论上,如果座位全为空,则不存在最近的人,因此这种情况需要特殊考虑。在实际应用中,可以通过检查`pos`列表是否为空来确定是否有座位被占用。如果`pos`为空,意味着没有任何座位被占用,可以返回座位数减1(即最右端的索引),因为此时任何座位到最近的人的距离都是无限大,但具体的返回值取决于题目的具体要求。

相关问题

考场就座

在考场里,一排有 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. 1 <= N <= 10^9
  2. 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
  3. 保证在调用 ExamRoom.leave(p) 时有学生正坐在座位 p 上。