用 Python 编写程序，查找空座位和已占用座位之间的最大距离

pythonserver side programmingprogramming更新于 2025/12/24 13:32:17

假设我们有一个仅包含 0 和 1 的列表，称为座位。其中 seat[i] 代表一个座位。当它是 1 时，则表示有人坐，否则表示空闲。至少有一个空座位和至少一个被占用的座位，我们必须找到从空座位到最近的被占用座位的最大距离。

因此，如果输入为座位 = [1, 0, 1, 0, 0, 0, 1]，则输出将为 2，因为我们可以占用座位 seat[4]，则距离为 2。

为了解决这个问题，我们将遵循以下步骤 −

res := 0
last := -1
n := 座位数
对于范围为 0 到 n - 1 的 i，执行
- 如果 seat[i] 为 1，则
  - res := res 和 (i 如果 last < 0 否则取 (i-last)/2 的下限) 的最大值
  - last := i
返回 res 和 (n-last-1) 的最大值

示例

让我们看看下面的实现以便更好地理解

def solve(seats):
   res, last, n = 0, -1, len(seats)
   for i in range(n):
      if seats[i]:
         res = max(res, i if last < 0 else (i - last) // 2)
         last = i
   return max(res, n - last - 1)

seats = [1, 0, 1, 0, 0, 0, 1]
print(solve(seats))