---
# System prepended metadata

title: 'Leetcode [No.1266] Minimum Time Visiting All Points'
tags: [leetcode]

---

# Leetcode [No.1266] Minimum Time Visiting All Points

## 題目

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

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

那這個距離又稱作[Chevshev distance](https://zh.wikipedia.org/zh-tw/切比雪夫距离)

```c++
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)


### 執行結果

![image](https://hackmd.io/_uploads/SJwY2-zLp.jpg)
