Skip to content

Latest commit

 

History

History
38 lines (27 loc) · 1.57 KB

1266.minimum-time-visiting-all-points.md

File metadata and controls

38 lines (27 loc) · 1.57 KB

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

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

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


限制条件,必须按照数组中出现的顺序来访问这些点。

也就是求每两个点之间的最小距离的和

切比雪夫距离

对于平面上的两个点 x = (x0, x1) 和 y = (y0, y1),设它们横坐标距离之差为 dx = |x0 - y0|,纵坐标距离之差为 dy = |x1 - y1|,则移动的最小次数分为三种情况

当 dx == dy, 沿对角线移动 dx 当 dx < dy, 需要沿对角线移动 dx, 沿竖直方向移动 dy - dx,总共移动 dy 次 当 dy < dx, 需要沿对角线移动 dy, 沿竖直方向移动 dx - dy,总共移动 dx 次

其实就是取 dx 和 dy 的较大值,这也被称作 x 和 y 之间的 切比雪夫距离

var minTimeToVisitAllPoints = function (points) {
  let distance = 0;
  for (let i = 1; i < points.length; i++) {
    let p = points[i - 1],
      q = points[i];
    distance += Math.max(Math.abs(p[0] - q[0]), Math.abs(p[1] - q[1]));
  }
  return distance;
};