【Leetcode Daily】1266访问所有点的最小时间

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个点集，在二维坐标系上，现在需要按顺序走过这些点，规定直走和斜走一个格子都算一个单位时间（秒），求最终的时间最小值。

思路分享

• 由于必须按顺序，所以只要考虑如何计算出两个点之间的最小距离即可。对于两点，举例 0，0 和 2，3，自然是斜着两次竖着一次最少，可以发现能斜着走就斜着走是最佳的方法（简单贪心？），所以可以先计算两点的 x y 差值，取最小的那个作为斜着走的步，剩下的无论横竖都直接加上即可。

• 思考完发现，既然最终的答案是先取最小差值，再加上最小差值与最大差值的差值，数值上直接与最大差值相等啊，这就是切比雪夫距离，代表国际象棋移动距离。

• 灵神一眼就看出这是切比雪夫距离，秒了。

  https://leetcode.cn/problems/minimum-time-visiting-all-points/solutions/3869961/qie-bi-xue-fu-ju-chi-pythonjavaccgojsrus-iw1l/?envType=daily-question&envId=2026-01-12

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        ans = 0
        for (x1, y1), (x2, y2) in pairwise(points):
            ans += max(abs(x1-x2), abs(y1-y2))
        return ans
        
        pre_x, pre_y = points[0]
        ans = 0
        if len(points) == 1:
            return ans

        for x, y in points[1:]:
            ans += max(abs(x-pre_x), abs(y-pre_y))
            pre_x, pre_y = x, y
        return ans