📘 題目敘述
給定一個二維平面上的點集合 points，其中 points[i] = [xi, yi] 表示第 i 個點的座標。
你一開始位於 points[0]，並且必須依序走訪 points[1]、points[2]、…、直到最後一個點。
在每一秒鐘，你可以進行以下其中一種移動：
- 水平移動 1 單位
- 垂直移動 1 單位
- 斜向移動 1 單位（同時改變 x 與 y）
請回傳走訪所有點所需的最少時間（秒數）。
條件限制
1 ≤ points.length ≤ 100points[i].length == 2-1000 ≤ xi, yi ≤ 1000
🧠 解題思路
這題的關鍵在於理解「斜向移動的效果」。
因為每一秒可以同時改變 x 與 y 各 1 單位，所以在移動兩個點 (x1, y1) → (x2, y2) 時：
- 可以盡量用「斜向移動」同時縮小
x與y的距離 - 當其中一個方向對齊後，再用直線移動補齊剩下的距離
因此，從一個點移動到下一個點的最少時間，其實只和 x 距離與 y 距離的最大值 有關。
關鍵觀察
假設目前在 (x, y)，要移動到 (nx, ny)：
dx = |nx - x|dy = |ny - y|
最佳策略是：
- 先用
min(dx, dy)次斜向移動 - 剩下
|dx - dy|次只能用水平或垂直移動
所以總時間為：max(dx, dy)
這也是為什麼不需要真的模擬每一步移動，只要計算距離即可。
所有變數
n：點的總數now：目前要前往的點的索引（從1開始）x, y：目前所在點的座標dx, dy：目前點與下一個點在 x、y 方向的距離ans：累積的最少移動時間
🪜 主要流程步驟
初始狀態
- 一開始位置設為
points[0] - 從第二個點開始，依序走訪後面的點
每一次移動的計算方式
對於「目前點 → 下一個點」：
- 計算
dx與dy - 本次最少需要的時間為
max(dx, dy) - 把這個時間加進
ans - 更新目前位置為下一個點
這樣一路累加，直到走訪完所有點。
為什麼可以直接相加？
- 必須依序走訪所有點
- 每一段移動都是獨立的
- 沒有回頭或路線選擇的問題
所以只要把每一段的最少時間加起來，就是整體的最少時間。
整體邏輯總結
- 斜向移動 = 同時減少 x 與 y 距離
- 每一段移動的最少時間 =
max(dx, dy) - 問題可以拆成「相鄰兩點之間」的距離計算
因此整體只需要一次線性掃描即可完成。
💻 程式碼實作
class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int n = points.size();
int now = 1;
int x = points[0][0], y = points[0][1];
int ans = 0;
while (now < n) {
int dx = abs(points[now][0] - x), dy = abs(points[now][1] - y);
ans += max(dx, dy);
x = points[now][0], y = points[now][1];
now += 1;
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/minimum-time-visiting-all-points/