多遍扫描变单次遍历,距离算法优化详解
2026-02-24 14:35:20
0浏览
收藏
本文深入剖析了如何将解决“最大化到最近人的距离”问题的暴力多遍扫描算法,重构为优雅高效的单次遍历方案:通过巧妙利用首个1的位置锚定左边界,仅用一次正向扫描动态维护上一个1的索引和当前最大距离,在O(n)时间与O(1)空间内精准计算左端、中间和右端三类最大安全距离,彻底消除冗余循环、模糊命名与边界错误,代码简洁度提升60%以上,堪称线性结构中“最近邻距离”问题的范式级解法——原来最优解,就藏在一次清醒的遍历之中。

本文详解如何将暴力多循环解法重构为高效单次遍历方案,通过一次扫描精准计算边界空位与中间最大间隔,显著提升可读性、时间复杂度(O(n))和代码简洁性。
本文详解如何将暴力多循环解法重构为高效单次遍历方案,通过一次扫描精准计算边界空位与中间最大间隔,显著提升可读性、时间复杂度(O(n))和代码简洁性。
在解决“最大化到最近人的距离”(LeetCode 849)问题时,核心目标是:给定一个仅含 0(空座)和 1(有人)的数组,找出一个空座位,使得该位置到最近已坐人位置的距离最大,并返回这个最大距离。
原始代码虽能通过测试用例,但存在明显缺陷:
- 使用了三次独立遍历(左端连续空位、右端连续空位、中间最大连续空位);
- 变量命名模糊(如 left_max, curr_count, max_count),逻辑耦合度高;
- 边界处理冗余(如手动 while 循环找首尾零段),易出错且难以维护;
- 中间空段距离计算错误:(max_count + 1) // 2 实际应为 max_count // 2(因两端均有参照人,最优位在正中,距离为间隔长度的一半向下取整)。
✅ 优化关键思路:
- 利用首次出现的 1 定位左边界起点(seats.index(1));
- 单次正向扫描,每次遇到新 1 时,更新当前最大安全距离为 (i - prev_pos) // 2;
- 统一处理右边界:若末尾为 0,则右端最大距离为 len(seats) - prev_pos - 1;
- 避免额外空间与重复计算,全程仅维护两个变量:prev(上一个 1 的索引)和 ans(当前最大距离)。
以下是优化后的 Python 实现(兼容 Python 3.9+,含类型提示):
from typing import List
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
# 找到第一个坐着的人的位置
prev = seats.index(1)
ans = prev # 左边界距离:从索引 0 到第一个 1 的距离
# 从第二个 1 开始遍历
for i in range(prev + 1, len(seats)):
if seats[i] == 1:
# 当前两人间距的一半即为这段中间区域的最大安全距离
ans = max(ans, (i - prev) // 2)
prev = i
# 处理右边界:如果最后一个座位是空的,则距离为 len(seats)-1 - prev
ans = max(ans, len(seats) - 1 - prev)
return ans? 算法正确性验证(以 [1,0,0,0,0,1,0,0,0,1] 为例):
- prev = 0,初始 ans = 0(左边界无空位);
- 遇到 i=5(seats[5]==1)→ (5-0)//2 = 2,ans = 2;
- 遇到 i=9(seats[9]==1)→ (9-5)//2 = 2,ans 仍为 2;
- 右边界:len(seats)-1-prev = 9-9 = 0 → 最终返回 2 ✅
⚠️ 注意事项:
- seats.index(1) 在输入保证至少有一个 1 的前提下安全,无需异常捕获;
- 整数除法 // 天然支持奇偶间隔:[0,0,1] 中两空位 → (2-0)//2 = 1;[0,1] → (1-0)//2 = 0,再由右边界 1-0 = 1 覆盖;
- 不要误用 (i - prev + 1) // 2 —— 距离基于索引差,而非元素个数。
? 总结:本优化方案将时间复杂度稳定在 O(n),空间复杂度 O(1),代码行数减少 60%+,逻辑主干清晰可读。它体现了经典“双指针扫描”思想——用一个状态变量(prev)记录关键锚点,在单次遍历中动态更新全局最优解,是处理线性结构中“最近邻距离”类问题的范式级解法。
到这里,我们也就讲完了《多遍扫描变单次遍历,距离算法优化详解》的内容了。个人认为,基础知识的学习和巩固,是为了更好的将其运用到项目中,欢迎关注golang学习网公众号,带你了解更多关于的知识点!
微信清理内存技巧,轻松释放手机空间
- 上一篇
- 微信清理内存技巧,轻松释放手机空间
- 下一篇
- PHP优化小程序请求速度的技巧与方法
查看更多
最新文章
-
- 文章 · python教程 | 2天前 | 线程池 · Python 线程池 concurrent.futures 任务取消 Future.cancel
- Python concurrent.futures.Future.cancel 怎样判断任务能否取消
- 143浏览 收藏
-
- 文章 · python教程 | 2天前 | 标准库 · HTTP服务 · 多线程 · Python教程 · Python 并发请求 http.server ThreadingHTTPServer ThreadingMixIn BaseHTTPRequestHandler
- Python http.server ThreadingHTTPServer 怎样处理并发请求
- 481浏览 收藏
-
- 文章 · python教程 | 2天前 |
- Python tarfile.TarInfo.replace 怎样复制归档成员属性
- 308浏览 收藏
-
- 文章 · python教程 | 2天前 | 并发编程 · Python教程 · Python 多进程 multiprocessing forkserver 启动上下文
- Python multiprocessing forkserver 怎样处理进程启动上下文
- 232浏览 收藏
-
- 文章 · python教程 | 2天前 | 标准库 · 异步编程 · Python教程 · Python asyncio StreamReader readexactly IncompleteReadError 异步流
- Python asyncio.StreamReader.readexactly 怎样处理不足长度的输入
- 427浏览 收藏
-
- 文章 · python教程 | 2天前 |
- Python operator.length_hint 怎样为未知长度迭代器设置估计值
- 336浏览 收藏
-
- 文章 · python教程 | 2天前 | 标准库 · Python教程 · Python warnings catch_warnings simplefilter filterwarnings 警告过滤
- Python warnings context manager 怎样临时调整警告过滤
- 255浏览 收藏
-
- 文章 · python教程 | 2天前 | 调试 · python · 异步编程 · Python asyncio introspection current_task all_tasks
- Python asyncio introspection 怎样定位当前任务
- 120浏览 收藏
-
- 文章 · python教程 | 2天前 | 标准库 · Python教程 · Python 类型注解 Python 3.14 annotationlib get_annotations ForwardRef 延迟注解
- Python 3.14 annotationlib.get_annotations 怎样读取延迟注解
- 423浏览 收藏
-
- 文章 · python教程 | 2天前 |
- Python 3.14 跨解释器 Queue.put 的阻塞与 QueueFull 处理方案
- 157浏览 收藏
-
- 文章 · python教程 | 3天前 | xml · python · Python xml xml.etree.ElementTree canonicalize C14N
- Python xml.etree.ElementTree.canonicalize 怎样生成稳定的 XML 文本
- 151浏览 收藏
查看更多
课程推荐
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 543次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 516次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 500次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 485次学习
查看更多
AI推荐
-
- PubMedQA
- 深入了解PubMedQA生物医学问答数据集,涵盖其核心功能、使用方法及在临床决策、药物研发等场景的应用,助力提升NLP模型性能。
- 1176次使用
-
- H2O EvalGPT
- H2O EvalGPT是H2O.ai推出的开源LLM评估平台,提供详细的大模型性能排行榜、行业特定基准测试及A/B测试功能,助您快速选择最适合项目的高性能大语言模型。
- 1161次使用
-
- LMArena
- LMArena是加州大学伯克利分校推出的AI模型匿名评测平台。通过盲测投票机制,用户可对比不同大模型回答并生成实时排行榜,助力开发者优化模型及用户选择最佳AI工具。
- 1344次使用
-
- HELM
- 深入了解斯坦福推出的HELM(Holistic Evaluation of Language Models)大模型评测体系。本文解析其核心功能、安装配置步骤及应用场景,涵盖准确性、公平性、鲁棒性等多维度指标,助力开发者全面优化语言模型性能。
- 1286次使用
-
- MMBench
- MMBench是由上海人工智能实验室等机构联合推出的多模态基准测试平台,提供细粒度能力评估、大规模数据集及VLMEvalKit工具。本文详细介绍其核心功能、安装使用方法及应用场景,助力开发者全面评估多模态模型性能。
- 1144次使用
查看更多
相关文章
-
- Python TaskGroup 怎样让子任务失败统一收敛
- 2026-11-12 501浏览
-
- Python xml.dom.minidom.unlink 怎样释放不再使用的 DOM 树引用
- 2026-10-27 501浏览
-
- Python typing 怎样用 TypeIs 缩小类型
- 2026-10-24 501浏览
-
- Python sqlite3 Connection serialize 怎么导出数据库快照:备份窗口、内存占用与恢复校验
- 2026-08-26 501浏览
-
- Python监控网页状态:requests异常处理实战
- 2026-05-29 501浏览

