当前位置：首页 > news >正文

LeetCode 1266.访问所有点的最小时间：贪心（数学）+python一行版

news 2026/3/27 4:25:43

【LetMeFly】1266.访问所有点的最小时间：贪心（数学）+python一行版

力扣题目链接：https://leetcode.cn/problems/minimum-time-visiting-all-points/

平面上有n个点，点的位置用整数坐标表示points[i] = [x_i, y_i]。请你计算访问所有这些点需要的最小时间（以秒为单位）。

你需要按照下面的规则在平面上移动：

每一秒内，你可以：
- 沿水平方向移动一个单位长度，或者
- 沿竖直方向移动一个单位长度，或者
- 跨过对角线移动sqrt(2)个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
必须按照数组中出现的顺序来访问这些点。
在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。

示例 1：

输入：points = [[1,1],[3,4],[-1,0]]输出：7解释：一条最佳的访问路径是：[1,1]-> [2,2] -> [3,3] ->[3,4]-> [2,3] -> [1,2] -> [0,1] ->[-1,0]从 [1,1] 到 [3,4] 需要 3 秒 从 [3,4] 到 [-1,0] 需要 4 秒 一共需要 7 秒

示例 2：

输入：points = [[3,2],[-2,2]]输出：5

提示：

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

解题方法：贪心

斜着移动一次相当于横着移动一次加竖着移动一次，点的访问顺序是固定的，所以从a点到b点时：

我们尽可能多地斜向移动，移动到一条水平线或竖直线时水平/竖直移动。
总移动次数：m a x ( 水平 d i f f , 竖直 d i f f ) max(水平diff, 竖直diff)max(水平diff,竖直diff)。相当于斜向移动时候把近的那个水平/竖直分量给一块走了。

时间复杂度O ( l e n ( p i n t s ) ) O(len(pints))O(len(pints))
空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-01-12 23:28:12 */classSolution{public:intminTimeToVisitAllPoints(vector<vector<int>>&points){intans=0;for(inti=1;i<points.size();i++){ans+=max(abs(points[i][0]-points[i-1][0]),abs(points[i][1]-points[i-1][1]));}returnans;}};

Python

''' LastEditTime: 2026-01-12 23:32:26 '''fromtypingimportListfromitertoolsimportpairwiseclassSolution:defminTimeToVisitAllPoints(self,points:List[List[int]])->int:returnsum(max(abs(a[0]-b[0]),abs(a[1]-b[1]))fora,binpairwise(points))

Java

/* * @LastEditTime: 2026-01-12 23:32:59 */classSolution{publicintminTimeToVisitAllPoints(int[][]points){intans=0;for(inti=1;i<points.length;i++){ans+=Math.max(Math.abs(points[i][0]-points[i-1][0]),Math.abs(points[i][1]-points[i-1][1]));}returnans;}}

Go

/* * @LastEditTime: 2026-01-12 23:35:23 */packagemainfuncabs1266(aint)int{ifa<0{return-a}returna}funcminTimeToVisitAllPoints(points[][]int)(ansint){fori:=1;i<len(points);i++{ans+=max(abs1266(points[i][0]-points[i-1][0]),abs1266(points[i][1]-points[i-1][1]))}return}

Rust

/* * @LastEditTime: 2026-01-12 23:37:10 */implSolution{pubfnmin_time_to_visit_all_points(points:Vec<Vec<i32>>)->i32{letmutans:i32=0;foriin1..points.len(){ans+=(points[i][0]-points[i-1][0]).abs().max((points[i][1]-points[i-1][1]).abs());}ans}}