访问所有点的最小时间

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

/*
 * 题目思路：
 * 我们需要计算访问所有点的最小时间，每次可以水平、竖直或者对角线移动。
 * 对于每两个点，我们可以水平或竖直移动的时间是它们的横纵坐标差的绝对值的较大值。
 * 使用Java Stream简化循环操作。
 */
import java.util.stream.IntStream;

public class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        return IntStream.range(1, points.length)
            .map(i -> {
                int deltaX = Math.abs(points[i][0] - points[i - 1][0]);
                int deltaY = Math.abs(points[i][1] - points[i - 1][1]);
                return Math.max(deltaX, deltaY);
            })
            .sum();
    }
}

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

O(n)

O(1)