本文详解如何将暴力多遍历的座位距离计算优化为一次线性扫描，通过巧妙利用索引和边界处理，显著提升代码可读性、时间效率与逻辑简洁性。
本文详解如何将暴力多遍历的座位距离计算优化为一次线性扫描，通过巧妙利用索引和边界处理，显著提升代码可读性、时间效率与逻辑简洁性。
在解决「到最近乘客的最大距离」（LeetCode 849）问题时，核心目标是：给定一个仅含 0（空座）和 1（有人）的数组，找出一个空位，使该位置到最近已坐人位置的距离最大，并返回这个最大距离。
原始实现虽功能正确，但存在明显冗余：
- 使用三次独立循环分别处理左端连续空座、右端连续空座、以及中间最长连续空座；
- 手动维护多个计数器（left_max, right_max, curr_count, max_count），逻辑分散且易错；
- 边界判断（如 seats[0] == 0）与循环嵌套增加理解成本；
- 对中间空段距离的计算 (max_count + 1) // 2 未与上下文语义对齐，缺乏直观性。
✅ 优化关键思路：
将问题拆解为三类候选位置——左边界起点、右边界终点、中间连续空段的中心点。只需一次正向扫描，动态追踪上一个 1 的位置 p，并在遇到下一个 1 时，立即计算二者之间空段的“安全半径”（即中点到任一端的距离），同时持续更新全局最大值 c。
以下是优化后的专业实现：
from typing import List
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
# 找到第一个乘客的位置，作为初始参考点 p
p = seats.index(1)
c = p # 左端空座距离：从索引 0 到第一个 1 的距离
# 从 p+1 开始扫描剩余座位
for i in range(p + 1, len(seats)):
if seats[i] == 1:
# 当前乘客与上一乘客之间形成空段 [p+1, i-1]
# 中间最优位置是中点，距离为 (i - p) // 2
c = max(c, (i - p) // 2)
p = i # 更新上一个乘客位置
# 处理右端空座：从最后一个乘客 p 到末尾 seats[-1] 的距离
if seats[-1] == 0:
c = max(c, len(seats) - 1 - p)
return c✅ 为什么更优？
- 时间复杂度 O(n)，仅单次遍历：避免原始代码中最多三次遍历；
- 空间复杂度 O(1)：无额外数组或缓存；
- 逻辑内聚性强：c 始终代表当前已知的最大安全距离，p 始终是最近左侧乘客索引，语义清晰；
- 边界自然融合：左端距离由 seats.index(1) 初始化，右端距离在循环后统一判断，无需重复条件分支；
- 数学准确：(i - p) // 2 精确对应两乘客间最长空段的中点到任一端的距离（例如 [1,0,0,0,1] → i-p=4 → 4//2=2）。
? 注意事项：
- seats.index(1) 要求输入至少含一个 1（题目已保证），否则抛出 ValueError；
- 右端处理必须放在循环之后——若在循环中提前判断 seats[-1]，会错误触发多次计算；
- 整数除法 // 在 Python 中自动向下取整，恰好满足距离定义（如空段长为奇数 5 → 中点距两端均为 2；偶数 4 → 最优位置距左端 2、右端 2，仍为 2）。
? 总结：算法优化的本质不是“写得更短”，而是用更少的状态、更清晰的抽象、更一致的控制流，表达相同的问题逻辑。本例通过将“三类候选距离”统一建模为“上一乘客位置驱动的动态更新”，实现了可读性、健壮性与性能的同步提升——这正是高质量工程代码的典型范式。
