最大相邻差为什么算错了？从一个反例到 O(n) 桶算法

给一组乱序成绩，求按成绩排序后相邻两人的最大分差，看起来像一道“维护最大值”的题。但“遍历时前面出现过的最大值”和“排序后的前一名”是两个概念，混用它们会得到一个运行很快、答案却不对的程序。

本文整理并修订自我站的《C语言实现O(n)时间复杂度计算相邻成绩最大差异》。保留原问题和反例，用 Python 给出便于复现的修正版，补充正确性推导、边界检查与随机对照实验。修订重点是算法语义，不是对原文字句做润色。

一、先手算样例，再讨论复杂度

输入为 [2, 6, 8, 3, 15]。升序排列是 [2, 3, 6, 8, 15]，相邻差依次为 1、3、2、7，因此答案为 7。改成降序只会改变遍历方向，不会改变最大相邻分差。

原思路从左向右维护 maxScore，遇到更小的数就计算 maxScore - 当前值。处理到 3 时，maxScore 是 8，得到 5；处理到 15 时只更新最大值，最终返回 5。这个循环计算的是“保持输入顺序时，前面某个值到后面某个值的最大下降”，没有求出排序后的相邻差。

还有一个更短的反例：[1, 2, 3, 4] 的正确答案为 1，原循环返回 0；把同样的数倒过来，原循环返回 3。输入只是换了排列，目标答案本应不变。这种排列不变性，是检查此类统计问题的实用方法。

二、保留一个容易相信的参考实现

排序后比较相邻元素，逻辑直接，适合作为测试中的参考答案：

def sorted_oracle(values):
    ordered = sorted(values)
    return max((b - a for a, b in zip(ordered, ordered[1:])), default=0)

空数组和单元素数组没有相邻对，返回 0。这个版本不满足题目希望的线性时间目标，但实现路径与桶算法不同，可以帮助发现桶下标、边界和跳过空桶时的错误。测试里的排序开销不属于被测算法本身。

三、桶内只保留最小值和最大值

设元素数量为 n，最小值为 low，最大值为 high，跨度为 span = high - low。n 小于 2 或 span 为 0 时直接返回 0。其余情况下，排序后的 n-1 个相邻差之和等于 span，最大相邻差至少是平均差 span/(n-1)。因为输入是整数，答案至少为它的向上取整。

因此令桶宽 width = ceil(span/(n-1))。同一个桶中的整数最多相差 width-1，不可能形成最终的最大间隔；答案必定出现在相邻非空桶之间。只要记录每个桶的最小值和最大值，再按桶序扫描，用“本桶最小值 - 上一个非空桶最大值”更新答案即可。注意必须跳过空桶，不能把空桶当成数值 0。

样例中 span=13、n=5，桶宽为 4。四个桶依次覆盖 2～5、6～9、10～13、14～17；内容分别是 {2,3}、{6,8}、空、{15}。跨非空桶差为 6-3=3、15-8=7，答案为 7。

这里不是给每个分数都分配一个桶。桶数量为 span//width+1，且 width≥span/(n-1)，所以桶数不超过 n。即使输入只有 [0, 1000000000]，也只需要两个桶，不会按十亿分配数组。

四、可以直接运行的实现

函数接收有限可迭代对象，先复制为列表，因此不会修改调用者的原数组。本例只接受 Python 内建非负整数；布尔值、浮点数、字符串和负数都明确拒绝，避免把 True 当成成绩 1。输入校验放在长度判断之前，单元素非法输入也不会悄悄返回 0。

def maximum_gap(values):
    data = list(values)
    if any(type(x) is not int or x < 0 for x in data):
        raise ValueError("scores must be nonnegative built-in integers")
    n = len(data)
    if n < 2:
        return 0
    low, high = min(data), max(data)
    span = high - low
    if span == 0:
        return 0
    width = (span + n - 2) // (n - 1)
    count = span // width + 1
    mins = [None] * count
    maxs = [None] * count
    for value in data:
        i = (value - low) // width
        if mins[i] is None:
            mins[i] = maxs[i] = value
        else:
            mins[i] = min(mins[i], value)
            maxs[i] = max(maxs[i], value)
    answer = 0
    previous_max = None
    for bucket_min, bucket_max in zip(mins, maxs):
        if bucket_min is None:
            continue
        if previous_max is not None:
            answer = max(answer, bucket_min - previous_max)
        previous_max = bucket_max
    return answer

assert maximum_gap([2, 6, 8, 3, 15]) == 7
assert maximum_gap([1, 1, 1, 100]) == 99
assert maximum_gap([]) == 0

桶宽用整数除法计算，避免把大整数先转成浮点数再调用 ceil。Python 官方文档说明，int 支持任意精度，bool 是整数的子类型；这也是本例选择严格类型检查、且没有使用浮点中间值的原因。

在整数运算视为常数时间的常用模型下，复制、校验、找范围、入桶和扫描各需要 O(n) 时间，附加空间为 O(n)。若允许每个整数都极其巨大，Python 大整数运算的成本还取决于位数，不能把“任意精度”理解为“任意长度都能常数时间处理”。移植到 C/C++ 时，还要单独检查减法、向上取整加法与数组分配的溢出，不能直接照搬 Python 的数值假设。

五、让反例和对照测试约束实现

本次在 Python 3.14.6 本地执行了以下验证：10 组固定用例，包括空数组、单元素、重复值、升降序、极大间隔和大整数；原样例的全部 120 种排列；5 组非法输入；以及固定随机种子 20261112 的 5000 组随机数组。随机数组长度为 0～99，取值上界覆盖 2、10、1000、2**31 和 10**30，逐组与排序参考实现对比，全部通过。固定用例还检查了输入列表没有被修改。

核心对照方式如下，复制前面的两个函数后即可运行：

import random
rng = random.Random(20261112)
for trial in range(5000):
    bound = rng.choice([2, 10, 1000, 2**31, 10**30])
    values = [rng.randrange(bound) for _ in range(rng.randrange(100))]
    assert maximum_gap(values) == sorted_oracle(values), (trial, values)
print("5000 differential cases: PASS")

随机测试能补充覆盖，不能替代前面的正确性推导，也不代表做过生产性能压测。如果业务规模不大，先选排序版本往往更容易维护；只有确认线性时间是实际要求时，再承担桶算法的额外实现复杂度。

这次修订最有价值的一步，是先拿题目给的样例运行原循环。一个输出 5、预期 7 的反例，足以提醒我们：算法是否正确，应该先由问题定义和可复现实验回答，再讨论时间复杂度。

来源与参考

本站原文：https://www.cveoy.top/t/topic/hvoC
Python 官方文档，数值类型、整数精度与布尔类型：https://docs.python.org/3/library/stdtypes.html#numeric-types-int-float-complex