1266. 访问所有点的最小时间 #
- 标签:几何、数组、数学
- 难度:简单
题目大意 #
描述:给定 n
个点的整数坐标数组 points
。其中 points[i] = [xi, yi]
,表示第 i
个点坐标为 (xi, yi)
。可以按照以下规则在平面上移动:
- 每一秒内,可以:
- 沿着水平方向移动一个单位长度。
- 沿着竖直方向移动一个单位长度。
- 沿着对角线移动 $\sqrt 2$ 个单位长度(可看做在一秒内沿着水平方向和竖直方向各移动一个单位长度)。
- 必须按照坐标数组
points
中的顺序来访问这些点。 - 在访问某个点时,可以经过该点后面出现的点,但经过的那些点不算作有效访问。
要求:计算出访问这些点需要的最小时间(以秒为单位)。
说明:
- $points.length == n$。
- $1 \le n \le 100$。
- $points[i].length == 2$。
- $-1000 \le points[i][0], points[i][1] \le 1000$。
示例:
- 示例 1:
|
|
|
|
解题思路 #
思路 1:数学 #
根据题意,每一秒可以沿着水平方向移动一个单位长度、或者沿着竖直方向移动一个单位长度、或者沿着对角线移动 $\sqrt 2$ 个单位长度。而沿着对角线移动 $\sqrt 2$ 个单位长度可以看做是先沿着水平方向移动一个单位长度,又沿着竖直方向移动一个单位长度,算是一秒走了两步距离。
现在假设从 A 点(坐标为 (x1, y1)
)移动到 B 点(坐标为 (x2, y2)
)。
那么从 A 点移动到 B 点如果要想得到最小时间,我们应该计算出沿着水平方向走的距离为 dx = |x2 - x1|
,沿着竖直方向走的距离为 dy = |y2 - y1|
。
然后比较沿着水平方向的移动距离和沿着竖直方向的移动距离。
- 如果
dx > dy
,则我们可以先沿着对角线移动dy
次,再水平移动dx - dy
次,总共dx
次。 - 如果
dx == dy
,则我们可以直接沿着对角线移动dx
次,总共dx
次。 - 如果
dx < dy
,则我们可以先沿着对角线移动dx
次,再水平移动dy - dx
次,,总共dy
次。
根据上面观察可以发现:最小时间取决于「走的步数较多的那个方向所走的步数」,即 max(dx, dy)
。
根据题目要求,需要按照坐标数组 points
中的顺序来访问这些点,则我们需要按顺序遍历整个数组,计算出相邻点之间的 max(dx, dy)
,将其累加到答案中。
最后将答案输出即可。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。