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

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

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

输入样例： 第一行是长度N，第二行是N个以空格分隔的非负整数。

5
2 6 8 3 15

输出样例： 函数计算并返回有序化后，相邻的两名间最大的差异（第一名15，第二名8，差最大为7）。

7

函数接口定义：

int fun ( int D[],int N );

内容：

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

代码解析：

该函数使用了一个循环遍历数组，并维护两个变量：maxScore 和 maxDiff。maxScore 记录当前遍历到的最大成绩，maxDiff 记录当前遍历到的最大差异。

在循环中，如果当前遍历到的成绩 D[i] 大于 maxScore，则更新 maxScore。否则，计算当前成绩与 maxScore 的差值 diff，并与 maxDiff 进行比较，更新 maxDiff。

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

时间复杂度分析：

该函数只遍历数组一次，时间复杂度为 O(n)。

空间复杂度分析：

该函数只使用了几个常数大小的变量，空间复杂度为 O(1)。

总结：

该函数通过线性遍历数组，实现了在 O(n) 的时间和空间复杂度内计算相邻名次成绩的最大差异，是一种高效的算法。