C语言实现O(n)时间复杂度计算相邻成绩最大差异

可以使用一个桶排序的思想来实现在O(n)的时间和空间复杂度下计算相邻名次间成绩的最大差异。

首先，找到成绩数组中最大值max和最小值min。创建一个大小为max-min+1的桶数组，并初始化为0。

然后，遍历成绩数组，将每个成绩出现的次数记录到桶数组对应的位置上。即如果成绩为score，则将桶数组中下标为score-min的位置的值加1。

接着，遍历桶数组，找到相邻名次间成绩的最大差异。具体方法为：定义两个变量maxDiff和prevScore，分别表示最大差异和前一个出现的成绩。遍历桶数组，如果当前桶的值大于0，则表示该成绩出现过，更新maxDiff为当前成绩与prevScore的差值的最大值，并更新prevScore为当前成绩。

最后，返回maxDiff作为相邻名次间成绩的最大差异。

以下是具体的C语言代码实现：

#include <stdio.h>

int maxDifference(int scores[], int n) {
    if (n < 2) {
        return 0;
    }
    
    int max = scores[0];
    int min = scores[0];
    
    for (int i = 1; i < n; i++) {
        if (scores[i] > max) {
            max = scores[i];
        }
        if (scores[i] < min) {
            min = scores[i];
        }
    }
    
    int* bucket = (int*)malloc((max - min + 1) * sizeof(int));
    memset(bucket, 0, (max - min + 1) * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        bucket[scores[i] - min]++;
    }
    
    int maxDiff = 0;
    int prevScore = min;
    
    for (int i = 0; i < max - min + 1; i++) {
        if (bucket[i] > 0) {
            maxDiff = (i + min) - prevScore > maxDiff ? (i + min) - prevScore : maxDiff;
            prevScore = i + min;
        }
    }
    
    free(bucket);
    
    return maxDiff;
}

int main() {
    int scores[] = {3, 5, 1, 9, 7};
    int n = sizeof(scores) / sizeof(scores[0]);
    
    int maxDiff = maxDifference(scores, n);
    
    printf('Max Difference: %d\n', maxDiff);
    
    return 0;
}

这段代码首先定义了一个maxDifference函数来计算相邻名次间成绩的最大差异。在main函数中，我们定义了一个示例成绩数组scores，然后调用maxDifference函数计算最大差异并输出结果。

以上代码的时间复杂度为O(n)，空间复杂度为O(max-min+1)，满足题目要求。