526互联

[LeetCode] 1266. Minimum Time Visiting All Points

发布时间 2023-12-04 13:54:51作者: CNoodle

On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points.

You can move according to these rules:
In 1 second, you can either:
move vertically by one unit,
move horizontally by one unit, or
move diagonally sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).
You have to visit the points in the same order as they appear in the array.
You are allowed to pass through points that appear later in the order, but these do not count as visits.

Example 1:
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

访问所有点的最小时间。

平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间（以秒为单位）。
你需要按照下面的规则在平面上移动：
每一秒内，你可以：
沿水平方向移动一个单位长度，或者
沿竖直方向移动一个单位长度，或者
跨过对角线移动 sqrt(2) 个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
必须按照数组中出现的顺序来访问这些点。
在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。

思路

题目要我们求的是遍历 input 里所有的点所需要的最小时间，而且要按 input 数组里给的顺序。这道题问的最小时间有一点迷惑性，不是要我们求一个最优方案来得到这个最小时间，而是我们必须按照 input 数组里给的点的顺序来依次遍历，所以题目的最小时间其实是需要确保从某个点到下一个点的时间需要最小。

注意题目的定义，横坐标移动一格，纵坐标移动一格，以及对角线方向移动一格，代价都是 1，所以如果从某个点 A 移动到下一个点 B，这个最短距离是两者横坐标的差值和纵坐标的差值里较大的那个。在草稿纸上画一下就明白了。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int res = 0;
		int n = points.length;
		for (int i = 1; i < n; i++) {
			int[] prev = points[i - 1];
			int[] cur = points[i];
			int xDiff = Math.abs(cur[0] - prev[0]);
			int yDiff = Math.abs(cur[1] - prev[1]);
			res += Math.max(xDiff, yDiff);
		}
		return res;
    }
}