优化最大距离算法：单次扫描精简实现

本文深入剖析了LeetCode 849题“到最近乘客的最大距离”的算法优化过程，摒弃冗余的三遍扫描与分散的状态管理，创新性地采用单次线性扫描策略——仅维护上一个乘客位置p和当前最大安全距离c，便自然覆盖左端、中间、右端三类候选场景；代码简洁如诗，逻辑清晰如画，时间复杂度稳定O(n)、空间O(1)，更以精准的数学表达（如(i−p)//2）揭示距离本质，堪称工程实践中可读性、性能与健壮性完美统一的典范。

本文详解如何将暴力多遍历的座位距离计算优化为一次线性扫描，通过巧妙利用索引和边界处理，显著提升代码可读性、时间效率与逻辑简洁性。

本文详解如何将暴力多遍历的座位距离计算优化为一次线性扫描，通过巧妙利用索引和边界处理，显著提升代码可读性、时间效率与逻辑简洁性。

在解决「到最近乘客的最大距离」（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）。

? 总结：算法优化的本质不是“写得更短”，而是用更少的状态、更清晰的抽象、更一致的控制流，表达相同的问题逻辑。本例通过将“三类候选距离”统一建模为“上一乘客位置驱动的动态更新”，实现了可读性、健壮性与性能的同步提升——这正是高质量工程代码的典型范式。

以上就是《优化最大距离算法：单次扫描精简实现》的详细内容，更多关于的资料请关注golang学习网公众号！