1266. 訪問所有點的最小時間

思路

盡量斜著，否則直線移動。
斜的移動的步數是在水平變化跟垂直變化之間取最小。
剩下的則是直線。

貪心

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

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$