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

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

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

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

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

• 每一秒内，你可以：
  • 沿水平方向移动一个单位长度，或者
  • 沿竖直方向移动一个单位长度，或者
  • 跨过对角线移动 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点时：

我们尽可能多地斜向移动，移动到一条水平线或竖直线时水平/竖直移动。

总移动次数：$max(水平diff, 竖直diff)$。相当于斜向移动时候把近的那个水平/竖直分量给一块走了。

• 时间复杂度$O(len(pints))$
• 空间复杂度$O(1)$

AC代码

C++

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

Python

'''
LastEditTime: 2026-01-12 23:32:26
'''
from typing import List
from itertools import pairwise

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        return sum(max(abs(a[0] - b[0]), abs(a[1] - b[1])) for a, b in pairwise(points))

Java

/*
 * @LastEditTime: 2026-01-12 23:32:59
 */
class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        for (int i = 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]));
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2026-01-12 23:35:23
 */
package main

func abs1266(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func minTimeToVisitAllPoints(points [][]int) (ans int) {
    for i := 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
 */
impl Solution {
    pub fn min_time_to_visit_all_points(points: Vec<Vec<i32>>) -> i32 {
        let mut ans: i32 = 0;
        for i in 1..points.len() {
            ans += (points[i][0] - points[i - 1][0]).abs().max((points[i][1] - points[i - 1][1]).abs());
        }
        ans
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源