定西市网站建设_网站建设公司_代码压缩_seo优化

题目链接：1266. 访问所有点的最小时间（简单）

算法原理：

解法：找几何规律

1ms击败95.83%

时间复杂度O(N)

通过观察发现，我们只需要计算出两点间的差值即可，具体体现为👇

从点(x1,y1)到点(x2,y2)的过程中

水平距离dx=|x1-x2|，垂直距离dy=|y1-y2|

如果dx和dy同时>0，那么直接走对角线是最快的

dx>dy时，先沿对角线走dy秒，再水平走dx-dy秒，总共需要dx秒

dx<=dy时，先沿对角线走dx秒，再水平走dy-dx秒，总共需要dy秒

所以至少要花max(dx,dy)=max(|x1-x2|,|y1-y2|)

我们只需要枚举一遍两点，然后累加距离即可

Java代码：

class Solution { public int minTimeToVisitAllPoints(int[][] points) { int ret=0; for(int i=1;i<points.length;i++){ //获取前一个坐标(a,b) int a=points[i-1][0],b=points[i-1][1]; //获取当前坐标(x,y) int x=points[i][0],y=points[i][1]; ret+=Math.max(Math.abs(x-a),Math.abs(y-b)); } return ret; } }