leetcode题解--访问所有点的最小时间

这道题一到手，感觉高大上，第一反应是觉得好难，其实是个典型的扮猪吃老虎的题目，找对方法就很简单。

来！看题~

题目1266. 访问所有点的最小时间

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

题解：

我们来一步步吃掉它吧。

第一步

这道题的实际上是一道几何数学题，正确解法的第一步是要先画出直角坐标系，给坐标轴上所有坐标点画相对于坐标轴的平行线，就会形成一个个小正方形，然后按示例标好各点位置，自己试着走两步，接着就能发现其中奥秘。

第二步

在最小正方形上，从一个点到另一个相临点算一个时间单位，走最小正方形的对角线也是一个时间单位。两个点在坐标系上，总共只会有两种位置关系：在一条线上(包括相同点)、在矩形对角线上，而对角线又分为正方形和长方形这两种。

第三步

在一条线上，这个距离怎么算，从图上看就是线段长度；从数学上算，就是差值的绝对值；在正方形对角线上，因为最小正方形对角线算一个单位长度，所以这个时间值也可以按边长，也就是xy值任意一轴的差值绝对值；在长方形对角线上，这个时间值的算法可以先走一个长方形内最大正方形，走完后就在一条线上了，再走剩下的直线；你会发现，长方形内最大正方形的边长就是长方形最短边长，所以走到对角线上的点可以总结为最长边长；

第四步

经过上面分析，走完两点所有情况下的时间值，都可以总结为两点间形成的长方形(一条线上可以假设一条边为0)的最长边长值。按这种思路走完所有的点，再把每一段加起来就能得到最终结果了。

最后，上答案：

var minTimeToVisitAllPoints = function(points) {
  let res = 0
  for(let i = 0; i < points.length-1; i++){
    let next = points[i + 1]
    let cur = points[i]
    let diff = Math.max(Math.abs(cur[0] - next[0]), Math.abs(cur[1] - next[1]))
    res += diff
  }
  return res
}

这个解法还可以再优化下，每次循环少了一步points的长度-1的计算，能节省点时间

var minTimeToVisitAllPoints = function(points) {
  let res = 0
  for(let i = 1; i < points.length; i++){
    let last = points[i - 1]
    let cur = points[i]
    let diff = Math.max(Math.abs(cur[0] - last[0]), Math.abs(cur[1] - last[1]))
    res += diff
  }
  return res
}

复杂度

时间复杂度O(n)，其中 NN 是数组的长度。; 空间复杂度O(1);

题目链接：https://leetcode-cn.com/problems/minimum-time-visiting-all-points