Leetcode [No.1266] Minimum Time Visiting All Points

題目

https://leetcode.com/problems/minimum-time-visiting-all-points/

思路

一開始看到以為要用DP了，但是後來想想只要算兩點之間的距離加總就好，
，那因為我們的走法可以橫著走，所以兩點之間的距離最多就是x的距離或是y之間的距離。

那這個距離又稱作Chevshev distance

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

解法分析

• time complexity: O(nlgn)

執行結果