What is the key greedy idea in Maximum Distance in Arrays?

The greedy insight is that the largest distance must involve the smallest value from one array and the largest value from another. Because arrays are sorted, these values are simply the first and last elements, allowing a running global minimum and maximum to be maintained.

Why do we track extremes only from previous arrays?

Tracking extremes only from earlier arrays guarantees that any comparison with the current array uses elements from two different arrays. This preserves the constraint that both selected numbers cannot come from the same array.

Why are only the first and last elements of each array relevant?

Each array is sorted in ascending order, so the smallest element is at the beginning and the largest at the end. Any larger absolute difference must involve one of these boundaries rather than interior elements.

What is the time complexity of the optimal approach?

The optimal greedy scan processes each array once and performs constant work per array. This results in O(m) time complexity with O(1) extra space.

How does the greedy invariant prevent incorrect distances?

The invariant keeps the global minimum and maximum tied to arrays processed earlier. Distances are computed before updating these values, ensuring the current array never compares its own elements against itself.

#624

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

数组列表中的最大距离

给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。返回最大距离。示例 1：输入： [[1,2,3],[4,5],[1,2,3]] 输出： 4 解释…

数组贪心

题目描述

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

示例 1：

输入：[[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

示例 2：

输入：arrays = [[1],[1]]
输出：0

提示：

m == arrays.length
2 <= m <= 10⁵
1 <= arrays[i].length <= 500
-10⁴ <= arrays[i][j] <= 10⁴
arrays[i] 以升序排序。
所有数组中最多有 10⁵ 个整数。

lightbulb

解题思路

方法一：维护最大值和最小值

我们注意到，最大距离一定是两个数组中的一个最大值和另一个最小值之间的距离。因此，我们可以维护两个变量 $\textit{mi}$ 和 $\textit{mx}$ ，分别表示已经遍历过的数组中的最小值和最大值。初始时 $\textit{mi}$ 和 $\textit{mx}$ 分别为第一个数组的第一个元素和最后一个元素。

接下来，我们从第二个数组开始遍历，对于每个数组，我们首先计算当前数组的第一个元素和 $\textit{mx}$ 之间的距离，以及当前数组的最后一个元素和 $\textit{mi}$ 之间的距离，然后更新最大距离。同时，我们更新 $\textit{mi} = \min(\textit{mi}, \textit{arr}[0])$ 和 $\textit{mx} = \max(\textit{mx}, \textit{arr}[\textit{size} - 1])$ 。

遍历结束后，即可得到最大距离。

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

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        ans = 0
        mi, mx = arrays[0][0], arrays[0][-1]
        for arr in arrays[1:]:
            a, b = abs(arr[0] - mx), abs(arr[-1] - mi)
            ans = max(ans, a, b)
            mi = min(mi, arr[0])
            mx = max(mx, arr[-1])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Recognizes that sorted arrays mean only boundary values influence the maximum distance.
question_mark
Uses a running minimum and maximum from previously processed arrays.
question_mark
Explains why updating extremes after computing distances prevents using the same array twice.

warning

常见陷阱

外企场景

error
Updating the global minimum and maximum before computing distances, which can incorrectly compare values from the same array.
error
Attempting to compare all internal elements instead of using the sorted boundary property.
error
Forgetting to check both directions: current max minus global min and global max minus current min.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the pair of values that produces the maximum distance instead of just the distance.
arrow_right_alt
Modify the problem so arrays are not sorted, requiring preprocessing to find local minima and maxima.
arrow_right_alt
Extend the task to select k arrays and maximize the spread among chosen elements.

help

常见问题

外企场景

继续练习

#621 任务调度器 #630 课程表 III #632 最小区间