重排列表满足相邻差为M 最小化位置最大偏移算法题

给定一个整数列表（可视为数轴上的点序列），需生成一个与原列表等长、相邻元素差值等于给定整数M的新序列，新序列与原列表元素按下标一一对应，要求尽可能最小化「对应位置元素的绝对差值的最大值」，最终返回该最大值乘以2的结果。

• 列表长度范围：1 <= list_length <= 10^5
• 给定差值M范围：1 <= M <= 10^4
• 列表元素取值范围：-10^9 <= list[i] <= 10^9

用例1 #

original_list = [1, 2, 3, 4]
M = 2
生成的新序列 = [-0.5, 1.5, 3.5, 5.5]
// 对应位置绝对差值
diff = [1.5, 0.5, 0.5, 1.5]
max_of_diff = 1.5
return_val = 1.5 * 2 = 3 

用例2 #

original_list = [1, 2, 4, 3]
M = 2
生成的新序列 = [-1, 1, 3, 5]
// 对应位置绝对差值
diff = [2, 1, 1, 2]
max_of_diff = 2
return_val = 2 * 2 = 4 

首先明确核心性质：所有相邻元素差值固定为M的等长序列，一定是公差为M的等差数列，形式为 t, t+M, t+2M, ..., t+(n-1)*M，其中n是列表长度，t是可自由调整的序列首项。
我们的目标是选择合适的t，使得所有位置i的绝对差 |original[i] - (t + i*M)| 的最大值尽可能小。
对约束式子做变形，每个位置的要求可以写成：
|(original[i] - i*M) - t| <= D
其中D是要最小化的最大差值。上式等价于t必须落在区间 [original[i] - i*M - D, original[i] - i*M + D] 内，要存在满足所有位置约束的t，所有区间的交集必须非空。
可以推导出，最小的D恰好是 (max(c_i) - min(c_i)) / 2，其中 c_i = original[i] - i*M，此时t取 (min(c_i) + max(c_i))/2 即可让所有区间相交。题目要求返回D*2，刚好等价于 max(c_i) - min(c_i)，全程不需要浮点运算。
补充：如果题目允许相邻差值为负（即后一个元素比前一个小M，对应公差为-M的等差数列），用同样逻辑计算 c_i' = original[i] + i*M，得到 max(c_i') - min(c_i')，和公差为M的结果取最小值即可，从给出的测试用例看，默认公差为正即可通过。

def solve(original_list, M):
    n = len(original_list)
    max_c = -float('inf')
    min_c = float('inf')
    for i in range(n):
        c = original_list[i] - i * M
        max_c = max(max_c, c)
        min_c = min(min_c, c)
    res = max_c - min_c
    # 若需要考虑公差为-M的场景，打开以下注释取最小值
    # max_c = -float('inf')
    # min_c = float('inf')
    # for i in range(n):
    #     c = original_list[i] + i * M
    #     max_c = max(max_c, c)
    #     min_c = min(min_c, c)
    # res = min(res, max_c - min_c)
    return res

该解法时间复杂度O(n)，空间复杂度O(1)，可以稳定处理1e5长度的输入。

内容的提问来源于stack exchange，提问作者Akhoy