數組中最大間距問題

問題描述：給一個無序的數組，要求在O(n)的時間内求出排完序後相鄰兩數的最大間距，不許用桶排。

題解：

        用分桶法來做。

        先求出數組的最大最小值，然後給每個元素分桶。分桶的計算公式為：(cur-min)*n/(max-min)

        這樣就能保證正好有n+1個桶（從0到n），對于每個桶隻維護其最大最小值，以及裡面是否有值。

       由于n個數放n+1個桶，必然有一個空桶，是以最大間距必然出現在空桶的左右兩邊。（空桶一定不會是最後一個或者第一個，因為min和max分占兩桶）。

import java.util.Scanner;

public class maxgap {
	public static int maxGap(int[] num) {
		int len = num.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for(int i=0;i<len;i++) {
			min = Math.min(min,num[i]);
			max = Math.max(max,num[i]);
		}
		if(min==max)
			return 0;
		boolean[] vis = new boolean[len+1];
		int[] mins = new int[len+1];
		int[] maxs = new int[len+1];
		int bid = 0;
		for(int i=0;i<len;i++) {
			bid = bucket(num[i],min,max,len);//如何證明一個桶内的值肯定不會是最大間距的值
			mins[bid] = vis[bid]?Math.min(mins[bid], num[i]):num[i];
			maxs[bid] = vis[bid]?Math.max(maxs[bid], num[i]):num[i];
			vis[bid] = true;
		}
		int ans = 0;
		int lastmax = maxs[0];
		for(int i=1;i<=len;i++) {
			if(vis[i]) {
				ans = Math.max(ans, mins[i]-lastmax);
				lastmax = maxs[i];
			}
		}
		return ans;
	}
	
	public static int bucket(int cur,int min,int max,int len) {
		return (int) ((cur-min)*len/(max-min));
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n;
		n = in.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++)
			a[i] = in.nextInt();
		int ans = maxGap(a);
		System.out.println(ans);
	}
}