跳至主要內容

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

ITCharge大约 3 分钟

1266. 访问所有点的最小时间open in new window

  • 标签:几何、数组、数学
  • 难度:简单

题目大意

描述:给定 nn 个点的整数坐标数组 pointspoints。其中 points[i]=[xi,yi]points[i] = [xi, yi],表示第 ii 个点坐标为 (xi,yi)(xi, yi)。可以按照以下规则在平面上移动:

  1. 每一秒内,可以:
    1. 沿着水平方向移动一个单位长度。
    2. 沿着竖直方向移动一个单位长度。
    3. 沿着对角线移动 2\sqrt 2 个单位长度(可看做在一秒内沿着水平方向和竖直方向各移动一个单位长度)。
  2. 必须按照坐标数组 pointspoints 中的顺序来访问这些点。
  3. 在访问某个点时,可以经过该点后面出现的点,但经过的那些点不算作有效访问。

要求:计算出访问这些点需要的最小时间(以秒为单位)。

说明

  • points.length==npoints.length == n
  • 1n1001 \le n \le 100
  • points[i].length==2points[i].length == 2
  • 1000points[i][0],points[i][1]1000-1000 \le points[i][0], points[i][1] \le 1000

示例

  • 示例 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
输入:points = [[3,2],[-2,2]]
输出:5

解题思路

思路 1:数学

根据题意,每一秒可以沿着水平方向移动一个单位长度、或者沿着竖直方向移动一个单位长度、或者沿着对角线移动 2\sqrt 2 个单位长度。而沿着对角线移动 2\sqrt 2 个单位长度可以看做是先沿着水平方向移动一个单位长度,又沿着竖直方向移动一个单位长度,算是一秒走了两步距离。

现在假设从 A 点(坐标为 (x1,y1)(x1, y1))移动到 B 点(坐标为 (x2,y2)(x2, y2))。

那么从 A 点移动到 B 点如果要想得到最小时间,我们应该计算出沿着水平方向走的距离为 dx=x2x1dx = |x2 - x1|,沿着竖直方向走的距离为 dy=y2y1dy = |y2 - y1|

然后比较沿着水平方向的移动距离和沿着竖直方向的移动距离。

  • 如果 dx>dydx > dy,则我们可以先沿着对角线移动 dydy 次,再水平移动 dxdydx - dy 次,总共 dxdx 次。
  • 如果 dx==dydx == dy,则我们可以直接沿着对角线移动 dxdx 次,总共 dxdx 次。
  • 如果 dx<dydx < dy,则我们可以先沿着对角线移动 dxdx 次,再水平移动 dydxdy - dx 次,,总共 dydy 次。

根据上面观察可以发现:最小时间取决于「走的步数较多的那个方向所走的步数」,即 max(dx,dy)max(dx, dy)

根据题目要求,需要按照坐标数组 pointspoints 中的顺序来访问这些点,则我们需要按顺序遍历整个数组,计算出相邻点之间的 max(dx,dy)max(dx, dy),将其累加到答案中。

最后将答案输出即可。

思路 1:代码

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        ans = 0
        x1, y1 = points[0]
        for point in points:
            x2, y2 = point
            ans += max(abs(x2 - x1), abs(y2 - y1))
            x1, y1 = point
        
        return ans    

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(1)O(1)