到最近的人的最大距离

难度: Medium

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

Submission

运行时间: 32 ms

内存: 17.7 MB

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        pos = [p for p in range(len(seats)) if seats[p] == 1]
        if len(pos) == 1: # 考虑边界情况! 比如作差之前验证列表是否只有1个元素
            return max([pos[0]-0, len(seats)-1-pos[0]])
        dist = [pos[i+1]-pos[i] for i in range(len(pos)-1)]
        max_dist = max(dist)
        ans = int(max_dist/2)
        return max([ans, pos[0]-0, len(seats)-1-pos[-1]])

Explain

该题解采用的思路主要是找到所有已经有人坐的座位的下标，然后计算两者之间的最大空位数。首先，遍历整个座位数组，将所有有人的座位的下标存入列表pos中。如果pos中只有一个元素，即只有一个座位有人，直接计算该座位到数组两端的距离中的最大值。如果有多个有人的座位，计算相邻两个有人座位之间的距离，存入dist数组中。对于dist数组中的每个元素值，实际上代表了从一个有人的座位到下一个有人的座位之间的空座位数。这样，最远的可能距离将是dist中的最大值除以2（因为坐在两人正中间时距离最远）。最后，比较三种情况下的最大距离：1) 最左边的有人座位到数组开始的距离，2) 最右边的有人座位到数组结束的距离，3) dist数组中的最大值除以2。最终返回这三者之中的最大值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        # 获取所有有人的座位的索引
        pos = [p for p in range(len(seats)) if seats[p] == 1]
        # 特殊情况处理：只有一个有人的座位
        if len(pos) == 1:
            return max([pos[0]-0, len(seats)-1-pos[0]])
        # 计算相邻有人座位之间的距离
        dist = [pos[i+1]-pos[i] for i in range(len(pos)-1)]
        # 找到最大的距离，并除以2取整
        max_dist = max(dist)
        ans = int(max_dist/2)
        # 返回三种情况的最大值
        return max([ans, pos[0]-0, len(seats)-1-pos[-1]])

Explore

在计算最大距离时，将相邻有人座位之间的距离除以2是因为，如果希望找到离人最远的空座位，理想的位置是正好位于两个已坐人之间的中点。例如，如果有人的座位分别位于位置 0 和位置 10，那么位置 5（即中间位置）将是离两边人最远的位置。因此，除以2是为了找到这种中间位置，从而确保计算出的距离是从该空座位到最近的人的最大可能距离。

在题解中，如果座位序列的两端都是空的，则直接计算从序列两端到最近的有人座位的距离。这些距离是通过计算最左边有人的座位的索引（即列表中的第一个元素）和最右边有人的座位的索引（即列表中的最后一个元素）来得到的。最左边的距离是第一个有人的座位的索引值，而最右边的距离是座位总数减去最后一个有人的座位的索引再减1。这两个值分别代表了从数组开始和结束到最近有人座位的直接距离。

在只有一个有人的座位的情况下，该座位自然成为了分隔两段空座位的界限。此时，离这个有人座位最远的空座位必然位于数组的两端，因此，计算该座位到数组两端的距离，并取这两个距离中的最大值即可。这种处理方式是因为在只有一个有人的座位时，其他所有的座位都是空的，且这些空座位距离有人座位的远近就是直接的物理距离。

题解中的算法未直接提及当座位数组全为空（即`seats`数组全为0）的情况。理论上，如果座位全为空，则不存在最近的人，因此这种情况需要特殊考虑。在实际应用中，可以通过检查`pos`列表是否为空来确定是否有座位被占用。如果`pos`为空，意味着没有任何座位被占用，可以返回座位数减1（即最右端的索引），因为此时任何座位到最近的人的距离都是无限大，但具体的返回值取决于题目的具体要求。