最大间隙问题

Description

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

Input
输入数据的第1行有1个正整数n，n≤200000。
接下来的1行中有n个实数x1,x2,……,xn。

Output
将找到的最大间隙输出，保留1位小数。

Sample
Input
5
2.3 3.1 7.5 1.5 6.3

Output
3.2
Hint
注意：要 求 线 性 时 间 算 法

思路：很容易想到的做法排序然后相邻比较一遍更新答案，题目要求O(n),所以不行。
由于是在实数轴上面找最大间隙，我们可以先确定区间范围[min,max]，然后做等长划分即(max - min)/(n-1)，这样n个数就划分出来n-1个区间。去掉最大值和最小值，剩下n-2个数，n-1个区间放n-2个数，由鸽巢定理可知，必定由一个会空出来，那么最大间隙就是空着的区间后面的最小值-空着的区间前面的最大值。不过由于可能会空在第一个或者最后一个区间处理起来不太方便。所以直接扫一遍区间记录上一次区间最大值和当前区间最小值的差更新答案(满足相邻).
代码：

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
double a[maxn];
struct node{
	double M,m;
	int c;
	node(){
		c = 0;
		M = -inf;
		m = inf;
	}
};
node cnt[maxn];
int main(){
	int n;cin>>n;
	double Max = -inf,Min = inf;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		Max = max(Max,a[i]);//找最大值 
		Min = min(Min,a[i]);//找最小值 
	}
	double len = (Max - Min) * 1.0 / (n-1);// n-1 的长度 
	if(n == 2){
		printf("%.1lf\n",Max - Min);
		return 0;
	}
	for(int i=1;i<=n;i++){
		cnt[(int)((a[i] - Min) / len) + 1].c ++;
		cnt[(int)((a[i] - Min) / len) + 1].M = max(a[i],cnt[(int)((a[i] - Min) / len) + 1].M);//每段最大值 
		cnt[(int)((a[i] - Min) / len) + 1].m = min(a[i],cnt[(int)((a[i] - Min) / len) + 1].m);//每段最小值 
	}
	double ans = 0;
	double __min = Min;
	for(int i=1;i<=n-1;i++){
		if(cnt[i].c){
			if(cnt[i].m - __min > ans){
				ans = cnt[i].m - __min;
			}
			__min = cnt[i].M;
		}
	}
	if(Max - __min > ans){
		ans = Max - __min;
	}
	printf("%.1f\n",ans);
	return 0;
}