访问所有点的最小时间

难度: Easy

平面上有 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

Submission

运行时间: 26 ms

内存: 16.1 MB

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        count = 0
        len1 =len(points)
        for i in range(len1-1):
           a,b = points[i] 
           c,d = points[i+1]
           f = min(abs(a-c),abs(b-d))
           count += f 
           count += abs(a-c)-f  if abs(a-c)>abs(b-d) else abs(b-d)-f 
        return count

Explain

该题解利用了曼哈顿距离与切比雪夫距离的概念来计算两点间的最小时间。对于平面上的两点 (a, b) 和 (c, d)，水平或垂直移动一个单位时间为 1 秒，而对角移动也视为 1 秒。切比雪夫距离定义为 max(abs(a-c), abs(b-d))，这是因为在对角移动可以同时减少横纵坐标的差，直到其中一个坐标的差为 0，然后剩下的差需要单独水平或垂直移动。题解中，先计算的是两坐标差的最小值，即对角可同时减少的最大部分，然后计算剩余的部分，即两坐标差的较大值减去较小值，这部分只能单独水平或垂直移动。通过遍历所有点，累加每一步从一个点到下一个点需要的最小时间，就可以得到访问所有点的最小时间。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        count = 0  # 初始化时间计数器
        len1 = len(points)  # 点的总数
        for i in range(len1-1):  # 遍历每一对相邻的点
           a, b = points[i]  # 当前点
           c, d = points[i+1]  # 下一个点
           f = min(abs(a-c), abs(b-d))  # 对角线移动的最大可能次数
           count += f  # 对角线移动时间
           # 剩余需要单向移动的时间
           count += abs(a-c)-f if abs(a-c) > abs(b-d) else abs(b-d)-f
        return count  # 返回总时间

Explore

在这个题解的背景下，每次选择对角移动是最优的选择，因为对角移动同时减少了横坐标和纵坐标的差距，而且时间开销与单独的水平或垂直移动相同（都是1秒）。这意味着对角移动在效率上等同于单坐标的移动，但在效果上可以更快地减少两点间的距离。因此，当两个坐标的差都不为零时，选择对角移动可以更快地接近目标点，使得总的移动时间最短。

题解中计算对角线移动的最大可能次数是基于切比雪夫距离的定义，这并不是一种简单的估算，而是精确计算在给定的移动规则（水平、垂直、对角移动均耗时相同）下，从一个点到另一个点的最短时间。这种方法确实考虑了最优路径，即每一次都选择最优的移动方式（对角或水平/垂直）来最小化总移动时间。因此，这不仅是一种估算，而是在规定的时间模型下的精确计算。