0849. 到最近的人的最大距离【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 遍历

1. 📝 题目描述

• leetcode

给你一个数组 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^4
• seats[i] 为 0 或 1
• 至少有一个 空座位
• 至少有一个 座位上有人

2. 🎯 s.1 - 遍历

c

int maxDistToClosest(int* seats, int seatsSize) {
    int res = 0, last = -1;
    for (int i = 0; i < seatsSize; i++) {
        if (seats[i] == 1) {
            if (last == -1) res = i;
            else { int d = (i - last) / 2; if (d > res) res = d; }
            last = i;
        }
    }
    int d = seatsSize - 1 - last;
    if (d > res) res = d;
    return res;
}

js

/**
 * @param {number[]} seats
 * @return {number}
 */
var maxDistToClosest = function (seats) {
  const n = seats.length
  let res = 0,
    last = -1
  for (let i = 0; i < n; i++) {
    if (seats[i] === 1) {
      if (last === -1) res = i
      else res = Math.max(res, Math.floor((i - last) / 2))
      last = i
    }
  }
  res = Math.max(res, n - 1 - last)
  return res
}

py

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        n = len(seats)
        res = 0
        last = -1
        for i in range(n):
            if seats[i] == 1:
                if last == -1:
                    res = i
                else:
                    res = max(res, (i - last) // 2)
                last = i
        res = max(res, n - 1 - last)
        return res

• 时间复杂度：$O(n)$，其中 n 是座位数
• 空间复杂度：$O(1)$

算法思路：

• 记录上一个有人的位置，计算中间空位到两端的最大距离
• 特殊处理左端和右端的连续空位