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

有时，我们会关心相邻名次间成绩的差异，比如冠军与亚军差多少，第四名与第五名差多少等等。编写函数，计算模拟的成绩数组（均为非负整数，但是是无序的）中相邻的名次间成绩的最大差异（指按从高到低排序后，前一名较后一名相差的最大值）。显然，排序后再统计是一种方法，我们对时间效率有一定的要求：你能否在O(n)的时间和空间复杂度下完成该任务？你可以认为，数据数量少于2个时，差异认为是0。

代码实现

#include <stdio.h>

int fun(int D[], int N) {
    if (N < 2) {
        return 0;
    }
    
    int max_diff = 0;
    int max_score = D[0];
    
    for (int i = 1; i < N; i++) {
        int diff = max_score - D[i];
        if (diff > max_diff) {
            max_diff = diff;
        }
        if (D[i] > max_score) {
            max_score = D[i];
        }
    }
    
    return max_diff;
}

int main() {
    int N;
    scanf('%d', &N);
    
    int D[N];
    for (int i = 0; i < N; i++) {
        scanf('%d', &D[i]);
    }
    
    int max_diff = fun(D, N);
    printf('%d\n', max_diff);
    
    return 0;
}

代码解释

1. 函数定义: int fun(int D[], int N)，该函数接受两个参数：
   • D[]: 一个整数数组，代表成绩。
   • N: 整数数组的长度。
   • 函数返回值: 相邻名次间成绩的最大差异。
2. 边界条件: if (N < 2) { return 0; } 当数据数量少于2个时，直接返回0。
3. 循环遍历: 使用 for 循环遍历数组 D，从第二个元素开始 (i = 1)。
4. 计算差异: diff = max_score - D[i] 计算当前元素 D[i] 与当前最大值 max_score 之间的差异。
5. 更新最大差异: if (diff > max_diff) { max_diff = diff; } 如果当前差异 diff 大于之前记录的最大差异 max_diff，则更新 max_diff。
6. 更新最大值: if (D[i] > max_score) { max_score = D[i]; } 如果当前元素 D[i] 大于当前最大值 max_score，则更新 max_score。
7. 返回结果: 最后，函数返回 max_diff，即相邻名次间成绩的最大差异。

输入和输出样例

输入样例：

5
2 6 8 3 15

输出样例：

7

解释:

输入的数组为 [2, 6, 8, 3, 15]，经过排序后为 [15, 8, 6, 3, 2]。相邻两名间最大的差异出现在第一名（15）与第二名（8）之间，差值为 7。

总结

该算法通过一次遍历数组，在O(n)的时间复杂度内计算出相邻名次间成绩的最大差异，无需进行排序操作，效率更高。