⭐ 题目日期：

百度 - 2024/8/29

🌳 题目描述：

在一排座位中，1 代表有人坐在座位上，0 代表座位上是空的，seats[i] 表示第 i 个位置，题目保证至少有一个空座位和至少有一个人坐在座位上。用户的要求是坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上（即坐在离他最近的人最远的位置）并返回他到离他最近的人的最大距离。

示例 1：
输入：seats = [1, 0, 1, 0, 0, 0, 1, 1]
输出：2
解释图例：

示例 2：
输入：seats = [1, 0, 0, 0, 0]
输出：4
解释图例：

🕵🏽面试评估：

这道题考察候选人是否能够将问题模型转化成可执行的算法步骤，要求候选人识别和处理不同情况 - 左中右三个区域，即第一个有人坐的位置前面的空位；两个有人坐之间的空位；最后一个有人坐的位置后面的空位，并根据每种情况计算空座到最近坐人的最大距离。

🧗难度系数：

⭐️ ⭐️ ⭐

📝思路分析：

求解这道题，我们需要的是几个变量，result 记录结果，lastSeated 记录上一个坐人的位置（遍历结束之后为最后一个有坐人的位置）

根据上面图示的这三种情况：

• 情况一：第一个有人坐的位置前面的空位。针对情况一，在遍历过程中，我们遇到第一个有人坐的位置，此时距离是最大的，即从座位的起始位置到第一个坐人之间的距离
• 情况二：两个有人坐之间的空位。针对情况二，空座的最大距离是位于这两个坐人之间的中点。即用当前位置减去上一个有坐人的位置之前的距离除以 2，在每一次遍历中，我们更新最大值
• 情况三：最后一个有人坐的位置后面的空位。针对情况三，在遍历过程中，我们来到最后一个有人坐的位置，计算最后一个坐人位置到座位数组的末尾之间的距离

最后，将三种情况的距离取最大值即得出答案。

💻代码：

Java

    public int maxDistToClosest(int[] seats) {
        int lastSeated = -1;
        int result = 0;
        for (int i = 0; i < seats.length; i++) {
            if (seats[i] == 1) {
                if (lastSeated == -1) {
                    result = Math.max(result, i);
                } else {
                    result = Math.max(result, (i - lastSeated) / 2);
                }
                lastSeated = i;
            }
        }

        return Math.max(result, seats.length - 1 - lastSeated);
    }

Python

    def maxDistToClosest(self, seats: List[int]) -> int:
        last_seated = -1
        result = 0

        for i in range(len(seats)):
            if seats[i] == 1:
                if last_seated == -1:
                    result = max(result, i)
                else:
                    result = max(result, (i - last_seated) // 2)
                last_seated = i

        return max(result, len(seats) - 1 - last_seated)

🚵🏻复杂度分析：

时间复杂度：O(n), n 为数组的长度, 数组中的所有元素遍历一遍

空间复杂度：O(1), 代码中的变量都是常量级

🔬在线评测(Online Judge):

题目链接