How does the maximum of horizontal and vertical distances determine move time?

Using max(dx, dy) captures the optimal combination of diagonal and straight moves, minimizing seconds for each point pair.

Can I use only horizontal and vertical moves to solve this problem?

Yes, but it will overcount steps; diagonal moves reduce total time and are key to the minimal time solution.

What pattern does this problem represent in algorithms?

It follows the Array plus Math pattern, where array iteration is combined with simple coordinate arithmetic to compute results efficiently.

Does the solution scale for large arrays of points?

Yes, it runs in O(n) time and O(1) space, making it efficient for up to 100 points as per constraints.

How do I verify the output for points = [[1,1],[3,4],[-1,0]]?

Compute max differences for each consecutive pair: [1,1]->[3,4] gives 3, [3,4]->[-1,0] gives 4; sum to get total time 7 seconds.

#1266

Easy

auto_awesome数组·数学

LeetCode 题解工作台

访问所有点的最小时间

平面上有 n 个点，点的位置用整数坐标表示 points[i] = [x i , y i ] 。请你计算访问所有这些点需要的最小时间（以秒为单位）。你需要按照下面的规则在平面上移动：每一秒内，你可以：沿水平方向移动一个单位长度，或者沿竖直方向移动一个单位长度，或者跨过对角线移动 sqr…

数组数学几何

题目描述

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

你需要按照下面的规则在平面上移动：

每一秒内，你可以：
- 沿水平方向移动一个单位长度，或者
- 沿竖直方向移动一个单位长度，或者
- 跨过对角线移动 sqrt(2) 个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
必须按照数组中出现的顺序来访问这些点。
在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。

示例 1：

输入：points = [[1,1],[3,4],[-1,0]]
输出：7
解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒

示例 2：

输入：points = [[3,2],[-2,2]]
输出：5

提示：

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

lightbulb

解题思路

方法一：模拟

对于两个点 $p_1=(x_1, y_1)$ 和 $p_2=(x_2, y_2)$ ，横坐标和纵坐标分别移动的距离分别为 $d_x = |x_1 - x_2|$ 和 $d_y = |y_1 - y_2|$ 。

如果 $d_x \ge d_y$ ，则沿对角线移动 $d_y$ ，再沿水平方向移动 $d_x - d_y$ ；如果 $d_x < d_y$ ，则沿对角线移动 $d_x$ ，再沿竖直方向移动 $d_y - d_x$ 。因此，两个点之间的最短距离为 $\max(d_x, d_y)$ 。

我们可以遍历所有的点对，计算出每个点对之间的最短距离，然后求和即可。

时间复杂度 $O(n)$ ，其中 $n$ 为点的个数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        return sum(
            max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1])) for p1, p2 in pairwise(points)
        )

speed

复杂度分析

指标	值
时间	complexity is O(n) since each point pair is visited once. Space complexity is O(1) because no extra data structures proportional to n are used, only scalar accumulators.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
You may be asked to justify why diagonal moves are always optimal between two points.
question_mark
Clarify the relationship between horizontal and vertical distances for move counting.
question_mark
Expect questions linking array iteration with distance calculation, highlighting the Array plus Math pattern.

warning

常见陷阱

外企场景

error
Counting horizontal and vertical moves separately instead of using max(dx, dy) leads to overestimating time.
error
Ignoring diagonal moves can make solutions longer and fail efficiency expectations.
error
Off-by-one errors in computing differences between coordinates may cause incorrect totals.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing arbitrary order traversal changes the problem into a minimum path or traveling salesman variant.
arrow_right_alt
Restricting diagonal moves to only certain directions increases complexity and requires conditional logic.
arrow_right_alt
Expanding to 3D coordinates introduces an extra axis, still solvable with max differences but with three dimensions.

help

常见问题

外企场景

继续练习

#1232 缀点成线 #1453 圆形靶内的最大飞镖数量 #1037 有效的回旋镖