Array 1266 访问所有点的最小时间

2020-11-16

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

你可以按照下面的规则在平面上移动：

每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。必须按照数组中出现的顺序来访问这些点。

思路：

观察之后发现斜率的绝对值大于 1 ，小于 1，或者大于 1，在水平面上的方向不同，所需的时间不同。题解的思路是分为 2 种情况。

dx（x坐标差）和 dy（y坐标差）相等，时间差取得 dx 或者 dy。
dx 和 dy 谁大，时间差取谁。

public int minTimeToVisitAllPoints(int[][] points) {
       int x0 = points[0][0],y0 = points[0][1]
       int times = 0;
       for(int i = 1;i < points.length; i++){
           int x1 = points[i][0], y1 = points[i][1];
           int dx = Math.abs(x1-x0),dy = Math.abs(y1-y0);
           times += Math.max(dx,dy);
           x0 = x1;
           y0 = y1;
       
       }
       return times;
   }

事件复杂度：0（n）

空间复杂度：0（1）

方法一：切比雪夫距离

对于平面上的两个点 x = (x0, x1) 和 y = (y0, y1)，设它们横坐标距离之差为 dx = |x0 - y0|，纵坐标距离之差为 dy = |x1 - y1|，对于以下三种情况，我们可以分别计算出从 x 移动到 y 的最少次数：

dx < dy：沿对角线移动 dx 次，再竖直移动 dy - dx 次，总计 dx + (dy - dx) = dy 次；

dx == dy：沿对角线移动 dx 次；

dx > dy：沿对角线移动 dy 次，再水平移动 dx - dy 次，总计 dy + (dx - dy) = dx 次。

可以发现，对于任意一种情况，从 x 移动到 y 的最少次数为 dx 和 dy 中的较大值 max(dx, dy)，这也被称作 x 和 y 之间的切比雪夫距离。