LeetCode 5271. 访问所有点的最小时间 Minimum Time Visiting All Points

地址 https://leetcode-cn.com/problems/minimum-time-visiting-all-points/submissions/

题目描述
平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间（以秒为单位）。

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

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

样例

示例1

输入：points = [[,],[,],[-,]]

输出：

解释：一条最佳的访问路径是： [,] -> [,] -> [,] -> [,] -> [,] -> [,] -> [,] -> [-,]

从 [,] 到 [,] 需要  秒

从 [,] 到 [-,] 需要  秒

一共需要  秒

示例2

输入：points = [[,],[-,]]

输出：

提示：

points.length == n

 <= n <=

points[i].length ==

- <= points[i][], points[i][] <= 

算法1
若两点不在一条直线上 优先走斜线是最优的 同时减少横向和竖向的距离
走斜线意味着横向竖向同时增加相同单位
所以也意味着 走横向和竖向之差中 较小的值(走斜向)
然后再走横向和竖向之差中两个值得差(表示走竖向或者走横向)

C++ 代码

class Solution {

public:

    int minTimeToVisitAllPoints(vector<vector<int>>& points) {

        int sum = ;

        for(int i = ; i < points.size()-;i++){

            int xx =  abs(points[i][] - points[i+][]);

            int yy =  abs(points[i][] - points[i+][]);

            sum += min(xx,yy);

            sum += max(xx,yy) - min(xx,yy);

        }

        return sum;

    }

};