[Python]递归三部曲:线段树与滑动窗口最大值(19-21题全解析)

发布时间:2026/8/16 14:15:47
[Python]递归三部曲:线段树与滑动窗口最大值(19-21题全解析) 本文首发于 CSDN配套代码仓库Python_exercise_19适用人群有一定 Python 基础、想深入理解递归与数据结构的开发者 写在前面很多人在学习线段树时会遇到两个坎一是看不懂递归二是看得懂但写不出来。为了帮你跨过这两道坎我设计了这组“递归三部曲”​ 练习题围绕一个真实的 IoT 场景——鸿蒙网关乱序数据采集与实时告警​ 展开。第 20 题让你亲手用手画递归的每一步二分查找、区间分裂、线段树更新与查询建立直觉。第 21 题要求你把手工模拟的过程翻译成代码静态查询→动态更新→顺序滑动窗口实现“学以致用”。第 19 题将线段树嵌入乱序数据流的真实工程场景完成从理论到实践的飞跃。三题环环相扣核心思想只有一个——递归。如果你曾被递归折磨过这组题就是最好的“康复训练”。 题目总览编号题目名称领域核心知识点难度华为OD难度LeetCode角色19鸿蒙IoT网关数据采集与实时告警​数据结构·算法动态开点线段树、区间最大值查询、乱序数据流、滑动窗口⭐⭐⭐中等偏上Medium主任务​20扩展练习PyE19 补漏​手工模拟·代码填空二分查找手工模拟、区间分裂、线段树更新与查询手工模拟、边界条件处理、暴力法对比、代码填空⭐⭐简单~中等Easy-Medium辅助理解21扩展练习PyE19-2 补漏​基础实现·顺序窗口静态线段树查询、动态线段树更新、顺序滑动窗口最大值、复杂度对比⭐⭐⭐中等Easy-Medium辅助理解难度说明参照华为 OD 机试和 LeetCode 体系侧重数据结构与算法实现。 三大亮点为什么这组题值得刷亮点一递归思想贯穿始终三步彻底搞懂阶段题目做什么收获第一步用手画​第20题手工模拟二分查找、区间分裂、线段树更新与查询的每一步递归调用建立“分治”的肌肉记忆再也不怕递归第二步用代码写​第21题将手工模拟转化为递归函数实现动态开点线段树并应用于顺序滑动窗口理解递归如何自然地创建节点、回溯更新第三步用工程练​第19题在线段树基础上处理乱序数据流实现实时滑动窗口最大值掌握递归在真实场景中的应用应对面试高频题亮点二手工模拟 → 代码填空 → 独立实现层层递进第20题​ 分为七阶从“用手画”到“代码填空”再到“独立实现”确保你真正理解每一行代码背后的物理意义。第21题​ 在20题的基础上要求你从零写出线段树并立即应用到顺序滑动窗口问题实现“学以致用”。第19题​ 将线段树嵌入真实 IoT 场景处理乱序数据、窗口滑动、重复时间戳、负值等边界完成从理论到实践的飞跃。亮点三边界条件与性能优化并重第20题第四阶专门设置了边界条件手工计算重复时间戳、负值、空窗口防止你在代码中被动踩坑。第21题第四阶要求你进行复杂度对比理解“为什么需要线段树”以及“什么时候暴力法更快”。第19题的评分要点明确指出不仅要正确还要高效O(1) 均摊的单调队列解法可作为进阶挑战。 适合谁学✅已经掌握基础 Python 语法希望深入学习数据结构的开发者✅正在准备华为 OD 机试或大厂面试的求职者线段树和滑动窗口是高频考点✅对递归感到困惑想通过“手工模拟代码”彻底搞懂的学习者✅希望理解“从暴力到优化”思维过程的工程师 学习路线建议先做第 20 题的手工模拟拿出纸笔严格按照题目要求画出每一步的 left、right、mid画出区间分裂树画出线段树更新后的节点值变化。这一步至关重要它是后续所有代码的基础。完成第 20 题的代码填空与暴力实现填空能帮你检验对代码结构的记忆暴力实现则让你亲身体会“为什么需要优化”。进入第 21 题先实现静态线段树查询21-1再扩展为动态更新21-2然后封装成顺序滑动窗口类21-3最后进行复杂度对比21-4。挑战第 19 题在 21-3 的基础上增加乱序处理逻辑未来数据不可见。你可以先用暴力法验证正确性再尝试用线段树优化。进阶思考线段树查询是 O(log N)但第 19 题其实可以用单调队列做到 O(1) 均摊。如果你有兴趣可以尝试实现单调队列解法并对比两种方案的优劣。 文件结构. ├── README.md # 本文档 ├── 19_harmony_iot_gateway.py # 鸿蒙IoT网关数据采集与实时告警主任务 ├── 20_extend_exercise_pye19.py # 扩展练习PyE19 补漏 │ ├── 第一阶二分查找手工模拟 │ ├── 第二阶区间分裂与区间树 │ ├── 第三阶线段树更新与查询手工模拟 │ ├── 第四阶边界条件手工计算 │ ├── 第五阶暴力实现与复杂度对比 │ ├── 第六阶代码填空 │ └── 第七阶独立实现 └── 21_extend_exercise_pye19_2.py # 扩展练习PyE19-2 补漏 ├── 21-1静态线段树查询 ├── 21-2动态线段树更新 ├── 21-3顺序滑动窗口最大值 └── 21-4复杂度对比与思考 写在最后这三道题是我精心设计的“递归三部曲”希望能帮你彻底征服线段树和滑动窗口这两个高频考点。如果你在练习过程中有任何疑问或者发现了更好的实现方式欢迎在评论区留言交流觉得有用的话点个赞 再走吧 许可本项目仅供学习交流使用遵循 MIT License。

相关新闻