教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」LeetCode 题解系列中的一篇围绕 0573. 松鼠模拟 展开。该题属于「数组、数学」分类、难度中等核心在于把看似复杂的多轮取坚果问题通过数学归约转化为一个单变量最优选择问题再用贪心思路在 $O(n)$ 时间内求出最小移动距离。读完本文你将掌握「固定开销 可变项最小化」的推导技巧、曼哈顿距离在网格四方向移动下的应用以及一个可复制的 Python 参考实现。一、题目概览与题意拆解1.1 问题背景在二维平面上有一棵树、一只松鼠和若干坚果。松鼠需要将所有坚果收集到树的位置但每次只能携带一个坚果并且只能向上、下、左、右四个方向移动到相邻的单元格。求松鼠完成全部收集任务所需的最小移动次数。1.2 输入要素height、width平面的高度和宽度tree树的位置[tree_x, tree_y]squirrel松鼠的初始位置[squirrel_x, squirrel_y]nuts坚果位置列表[[nut1_x, nut1_y], [nut2_x, nut2_y], ...]。1.3 约束条件约束取值范围平面尺寸$1 \le height, width \le 100$树的位置tree.length 2松鼠位置squirrel.length 2坚果数量$1 \le nuts.length \le 5000$坚果坐标nuts[i].length 2行坐标范围$0 \le tree_r, squirrel_r, nut_r \le height$列坐标范围$0 \le tree_c, squirrel_c, nut_c \le width$这里的距离指移动的次数。由于只能在四个方向上移动两点之间的最短移动次数就是曼哈顿距离$dist(P, Q) |P_x - Q_x| |P_y - Q_y|$。1.4 示例验证示例 1输入height 5, width 7, tree [2,2], squirrel [4,4], nuts [[3,0], [2,5]] 输出12 解释为实现最小的距离松鼠应该先摘 [2, 5] 位置的坚果。示例 2输入height 1, width 3, tree [0,1], squirrel [0,0], nuts [[0,2]] 输出3二、解题思路贪心算法2.1 关键观察把整个收集过程分解开来看可以提炼出两条决定性事实除第一个坚果外其余坚果的收集路径完全相同当松鼠从树出发去取某一颗坚果时无论先后顺序如何路径都是「树 → 坚果 → 树」单颗成本恒为 $2 \times dist(tree, nut)$只有第一个坚果是特例松鼠最初并不在树下第一个坚果的路径是「松鼠 → 坚果 → 树」成本为 $dist(squirrel, nut) dist(nut, tree)$。这意味着后续坚果的收集顺序对总距离没有任何影响全部是固定开销唯一的决策自由度在于「第一个坚果选哪颗」。2.2 数学推导总距离公式设共有 $n$ 颗坚果总距离可表示为$$ Total \sum_{i0}^{n-1} 2 \times dist(tree, nuts[i]) ; - ; dist(tree, first_nut) ; ; dist(squirrel, first_nut) $$其中 $\sum_{i0}^{n-1} 2 \times dist(tree, nuts[i])$ 是假设所有坚果都「从树出发」的基准开销固定不变而 $dist(tree, first_nut)$ 与 $dist(squirrel, first_nut)$ 仅与第一个坚果相关。整理后第一个坚果带来的「额外代价」为$$ \Delta(nut) dist(squirrel, nut) - dist(tree, nut) $$总距离 固定部分 $ \min_{nut} \Delta(nut)$。2.3 贪心策略选择使差值最小的坚果作为第一个为了最小化总距离应选择使 $dist(squirrel, nut) - dist(tree, nut)$最小的坚果作为第一个收集的对象。以示例 1 验证tree [2,2]squirrel [4,4]nuts [[3,0], [2,5]]。坚果$dist(tree, nut)$$dist(squirrel, nut)$$\Delta$[3,0]$|2-3||2-0|3$$|4-3||4-0|5$$2$[2,5]$|2-2||2-5|3$$|4-2||4-5|3$$0$基准开销 $2 \times (3 3) 12$最小差值 $\min \Delta 0$总距离 $ 12 0 12$与题给输出一致——先摘[2, 5]位置的坚果确实最优。示例 2 同理基准 $2 \times 1 2$$\Delta dist([0,0],[0,2]) - dist([0,1],[0,2]) 2 - 1 1$总距离 $ 2 1 3$。2.4 正确性论证为什么这是精确解而非近似需要特别说明本题的「贪心」不是通常意义上的启发式近似而是精确的最优决策。原因在于除第一个坚果外其余成本全部是常数项$2 \times dist(tree, nut)$与顺序无关问题只有一个变量——第一个坚果的选择因此枚举所有候选坚果、取 $\Delta$ 最小值就是在有限集合上做精确最小化不存在「局部最优 ≠ 全局最优」的风险。从贪心算法的理论框架看可对照 贪心算法章节本题天然满足贪心选择性质每一步只需做当前最优选择即选差值最小的坚果先摘与最优子结构第一个坚果确定后剩余子问题为从树出发的固定开销其最优解即为常数求和因此贪心策略可以直接得出全局最优解。三、参考实现与逐段解析3.1 完整代码from typing import List class Solution: def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) - int: # 计算曼哈顿距离 def manhattan_distance(p1, p2): return abs(p1[0] - p2[0]) abs(p1[1] - p2[1]) # 计算所有坚果到树的距离之和的两倍假设都从树出发 total_distance 0 for nut in nuts: total_distance 2 * manhattan_distance(tree, nut) # 找到最优的第一个坚果 # 第一个坚果的额外距离是dist(squirrel, nut) - dist(tree, nut) min_diff float(inf) for nut in nuts: diff manhattan_distance(squirrel, nut) - manhattan_distance(tree, nut) min_diff min(min_diff, diff) return total_distance min_diff3.2 代码逐段解析内层工具函数manhattan_distance(p1, p2)直接按四方向移动的距离定义实现即两坐标差的绝对值之和第一遍循环累加 $2 \times dist(tree, nut)$构造总距离的固定基准部分。注意height、width参数在此并未参与计算因为曼哈顿距离只依赖坐标差值网格边界不影响两点的最短路径长度第二遍循环对每颗坚果计算 $\Delta dist(squirrel, nut) - dist(tree, nut)$用min_diff记录最小值。float(inf)作为初始值保证首个比较必然更新返回值total_distance min_diff即最小总移动距离。若min_diff为负松鼠离某颗坚果比树更近它还会从固定开销中扣除一部分完全符合公式推导。3.3 一趟遍历的等价写法两遍循环的目的是先凑齐固定部分、再找最小差值由于两部分的累加互不依赖也可以合并为单次遍历逻辑等价且更紧凑from typing import List class Solution: def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) - int: def manhattan_distance(p1, p2): return abs(p1[0] - p2[0]) abs(p1[1] - p2[1]) total_distance 0 min_diff float(inf) for nut in nuts: total_distance 2 * manhattan_distance(tree, nut) diff manhattan_distance(squirrel, nut) - manhattan_distance(tree, nut) min_diff min(min_diff, diff) return total_distance min_diff四、复杂度分析时间复杂度$O(n)$其中 $n$ 是坚果数量。只需遍历坚果列表一到两次每次计算均为常数次算术运算不随平面尺寸height × width增长空间复杂度$O(1)$仅使用total_distance、min_diff等常数额外空间未借助任何与输入规模相关的辅助结构。在约束上限 $n 5000$ 下该解法性能绰绰有余同时由于不依赖平面尺寸即使height、width增大也不影响开销。五、总结与延伸阅读5.1 题目在仓库中的定位本题目解收录于「算法通关手册」的 0500-0599 题解目录在 LeetCode 题解总列表 中标记为「数组、数学」分类、难度中等。其解题脉络属于 基础算法 - 贪心算法 的应用场景通过「问题转化 → 贪心策略制定 → 最优子结构利用」三步走把一个多轮路径规划问题化简为单点最小化问题。5.2 方法要点回顾识别出「除第一个坚果外其余成本全部固定」这一结构把问题归约为仅含一个变量的最小化用曼哈顿距离刻画四方向网格中的移动成本选择 $dist(squirrel, nut) - dist(tree, nut)$ 最小的坚果作为第一个收集对象用 $O(n)$ 遍历完成计算$O(1)$ 空间即可求解。5.3 同类拓展仓库中还收录了多道以曼哈顿距离为计量基础的题目可作为横向对比练习最佳见面地点在网格上求使所有人汇聚的曼哈顿距离总和最小点逃离幽灵利用曼哈顿距离比较玩家与幽灵到达终点的先后找到最近的有相同 X 或 Y 坐标的点在候选点集中按曼哈顿距离求最近点。这三道题与「松鼠模拟」共享同一套距离模型但优化目标各不相同适合用来巩固「识别固定开销、化归单变量」的数学建模能力。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 296「最佳的碰头地点」曼哈顿距离与中位数优化详解AlgoNote 算法通关手册LeetCode 296「最佳的碰头地点」曼哈顿距离与中位数优化详解 「最佳的碰头地点」LeetCode 296标签数组、教程文档知识库InternVL num_patches_list参数详解多图像推理的隐藏关键InternVL num_patches_list参数详解多图像推理的隐藏关键 InternVL 是接近 GPT 4o 表现的开源多模态大模型其 num_pLeetCode-Go 题解剖析1030. Matrix Cells in Distance Order 的曼哈顿距离排序解法LeetCode Go 题解剖析1030. Matrix Cells in Distance Order 的曼哈顿距离排序解法 矩阵类题在 LeetCode示例工程上一篇Hatch FAQ 深度解读互操作性、工具迁移路径与快速 CLI 的实现原理下一篇如何通过智能线程调度提升CPU性能CPUDoc完整使用教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考