最大间隙问题

最大间隙问题

时间： 1ms        内存：64M

描述：

最大间隙问题：给定n个实数x₁,x₂,……,x_n，求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整方法耗时O(1)，设计解最大间隙问题的线性时间算法。对于给定的n 个实数x₁,x₂,……,x_n，计算它们的最大间隙。

输入：

输入数据的第1行有1个正整数n，n≤200000。接下来的1行中有n个实数x₁,x₂,……,x_n。

输出：

将找到的最大间隙输出.

示例输入：

5
2.3 3.1 7.5 1.5 6.3

示例输出：

3.2

提示：

参考答案（内存最优[3132]）：

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
int main()
{
    int n;
    double maxnum=0;
    cin >> n;
    double data[200000]={0};
    for(int i=0;i<n;i++)
    {
        cin >> data[i];
    }
    sort(data,data+n);
    for(int i=0;i<n-1;i++)
    {
        double x = (data[i+1]-data[i]);
        if(x<0)
            x = -x;
        if(x>maxnum)
            maxnum = x;
    }
    printf("%g\n",maxnum);
    return 0;
}

参考答案（时间最优[104]）：

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
double a[2000005],maxx;
int main()
{
    long int n;
    scanf("%ld",&n);
    for(int i=0;i<n;i++)scanf("%lf",a+i);
    sort(a,a+n);
    for(int i=1;i<n;i++)
    {
        maxx=a[i]-a[i-1]>maxx?a[i]-a[i-1]:maxx;
    }
    printf("%g\n",maxx);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。