2020 年第 41 题

题目描述

给定三个非空递增序列 S1、S2、S3，请从每个序列中各取一个元素 a、b、c，使得距离

D = |a - b| + |b - c| + |c - a|

最小。

解题思路

先化简公式。

设三者中最小值为 min_v，最大值为 max_v，则：

D = 2 * (max_v - min_v)

因此问题转化为：如何让三个数的最大值和最小值尽量接近。

由于三个序列都是递增的，可以用三个指针：

1. 计算当前三个指针指向元素形成的距离。
2. 记录最优答案。
3. 每次只移动当前最小值所在的那个指针，因为只有它前进，才可能缩小 max - min。
4. 某个序列走完后结束。

手算示例

S1 = [1, 4, 10]

S2 = [2, 15, 20]

S3 = [10, 12]

(1, 2, 10) -> D = 18，最小值在 S1，移动 S1
(4, 2, 10) -> D = 16，最小值在 S2，移动 S2
(4, 15, 10) -> D = 22，最小值在 S1，移动 S1
(10, 15, 10) -> D = 10，更新答案

最优答案为 10

Python 实现

def min_distance_three_sorted(a, b, c):
    i = j = k = 0
    ans = float("inf")

    while i < len(a) and j < len(b) and k < len(c):
        x, y, z = a[i], b[j], c[k]
        current = abs(x - y) + abs(y - z) + abs(z - x)
        ans = min(ans, current)

        min_val = min(x, y, z)
        if min_val == x:
            i += 1
        elif min_val == y:
            j += 1
        else:
            k += 1

    return ans

复杂度分析

• 时间复杂度：O(l + m + n)
• 空间复杂度：O(1)

易错点

• 三个指针不是乱动，而是每次只移动最小值对应的指针。
• 一旦某个序列遍历完，就无法再组成三元组，应立即结束。
• 公式化简后更容易理解为什么这样移动是对的。

对应题

来源	题目	相似度	主要差异
LeetCode	632. 最小区间	100%	题面不同，本质一致

难度

⭐️⭐️⭐️⭐️⭐️