Easy

题目描述

在一个二维平面上，有 n 个整数坐标的点 points[i] = [xi, yi]。返回按照 points 给出的顺序访问所有点所需的最小时间（以秒为单位）。

你可以按照下面的规则移动：

在 1 秒内，你可以：

  • 垂直移动一个单位，
  • 水平移动一个单位，或者
  • 对角移动 sqrt(2) 个单位（换句话说，在 1 秒内垂直移动一个单位然后水平移动一个单位）。

你必须按照数组中出现的顺序访问这些点。 你可以经过稍后在顺序中出现的点，但这些不算作访问。

示例 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 秒

示例 2：

输入：points = [[3,2],[-2,2]]
输出：5

约束：

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

解题思路

这道题的关键是理解最优移动策略。从点A到点B的最短时间是什么？

核心思路：

  1. 可以同时进行水平和垂直移动（对角移动），这样最高效
  2. 对于两点间的移动，最优策略是：先尽可能多地对角移动，然后沿着剩余的方向直线移动

分析移动时间：

  • 设两点间的水平距离为 dx = |x2 - x1|，垂直距离为 dy = |y2 - y1|
  • 对角移动可以同时减少水平和垂直距离，可以移动 min(dx, dy) 次
  • 剩余距离为 |dx - dy|，需要直线移动这么多次
  • 因此总时间为：min(dx, dy) + |dx - dy| = max(dx, dy)

这个公式很关键：两点间的最短移动时间就是水平距离和垂直距离的最大值！

算法步骤：

  1. 遍历相邻的点对
  2. 计算每对点之间的最短移动时间
  3. 累加所有移动时间

代码实现

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int totalTime = 0;
        for (int i = 1; i < points.size(); i++) {
            int dx = abs(points[i][0] - points[i-1][0]);
            int dy = abs(points[i][1] - points[i-1][1]);
            totalTime += max(dx, dy);
        }
        return totalTime;
    }
};

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        total_time = 0
        for i in range(1, len(points)):
            dx = abs(points[i][0] - points[i-1][0])
            dy = abs(points[i][1] - points[i-1][1])
            total_time += max(dx, dy)
        return total_time

public class Solution {
    public int MinTimeToVisitAllPoints(int[][] points) {
        int totalTime = 0;
        for (int i = 1; i < points.Length; i++) {
            int dx = Math.Abs(points[i][0] - points[i-1][0]);
            int dy = Math.Abs(points[i][1] - points[i-1][1]);
            totalTime += Math.Max(dx, dy);
        }
        return totalTime;
    }
}

var minTimeToVisitAllPoints = function(points) {
    let totalTime = 0;
    for (let i = 1; i < points.length; i++) {
        const dx = Math.abs(points[i][0] - points[i-1][0]);
        const dy = Math.abs(points[i][1] - points[i-1][1]);
        totalTime += Math.max(dx, dy);
    }
    return totalTime;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有相邻点对，n为点的数量
空间复杂度O(1)只使用常数额外空间