1266. Minimum Time Visiting All Points

# 1266. Minimum Time Visiting All Points#

## 题目 #

On a plane there are `n` points with integer coordinates `points[i] = [xi, yi]`. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

• In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
• You have to visit the points in the same order as they appear in the array.

Example 1:

``````Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Time from [1,1] to [3,4] = 3 seconds
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds
``````

Example 2:

``````Input: points = [[3,2],[-2,2]]
Output: 5
``````

Constraints:

• `points.length == n`
• `1 <= n <= 100`
• `points[i].length == 2`
• `-1000 <= points[i][0], points[i][1] <= 1000`

## 题目大意 #

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

• points.length == n
• 1 <= n <= 100
• points[i].length == 2
• -1000 <= points[i][0], points[i][1] <= 1000

## 解题思路 #

• 在直角坐标系上给出一个数组，数组里面的点是飞机飞行经过的点。飞机飞行只能沿着水平方向、垂直方向、45°方向飞行。问飞机经过所有点的最短时间。
• 简单的数学问题。依次遍历数组，分别计算 x 轴和 y 轴上的差值，取最大值即是这两点之间飞行的最短时间。最后累加每次计算的最大值就是最短时间。

## 代码 #

``````
package leetcode

func minTimeToVisitAllPoints(points [][]int) int {
res := 0
for i := 1; i < len(points); i++ {
res += max(abs(points[i][0]-points[i-1][0]), abs(points[i][1]-points[i-1][1]))
}
return res
}

``````

Apr 8, 2023