ac (桶排序)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
//        int n = 4;
//        int[] arr = {9, 3, 1, 10};
//        int[] arr = {5,5,5,5};
        // O(n) 求出整体的最大最小值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            if(arr[i] > max){
                max = arr[i];
            }
            if(arr[i] < min){
                min = arr[i];
            }
        }
        if(max == min){
            System.out.println(0);
            return;
        }
        // 构造 桶 的区间, 桶个数是 n
        int span;
        if( (max - min) % n == 0){
            span = (max - min) / n;
        }else {
            span = (max - min) / n + 1;
        }

        // 每个buckets内部，buckets 之间
        // 初始化 buckets
        long[][] buckets = new long[n][3];
        for(int i=0;i<n;i++){
            buckets[i][0] = Long.MAX_VALUE; // 最小
            buckets[i][1] = Long.MIN_VALUE; // 最大
            buckets[i][2] = 0; // 0 表示bucket中的数量
        }

        long ans = Integer.MIN_VALUE; // 最后结果
        // 求出每个 buckets, 同时可以求出：桶内部相差的最大值
        for(int i=0;i<n;i++){
//            int pos = indexOf(range, n+1, arr[i]);
            int pos = indexOfBuckets(min, max, arr[i], span);
            if(arr[i] < buckets[pos][0]){
                buckets[pos][0] = arr[i];
            }
            if(arr[i] > buckets[pos][1]){
                buckets[pos][1] = arr[i];
            }
            // 最大 - 最小
            if((buckets[pos][1] - buckets[pos][0]) > ans){
                ans = buckets[pos][1] - buckets[pos][0];
            }
            buckets[pos][2] ++;
        }
        // 查看构造的 buckets
//        for(int i=0;i<n;i++){
//            System.out.println(buckets[i][0] + " " + buckets[i][1] + " " + buckets[i][2]);
//        }
        // 再求buckets之间
        int bi = 0;
        int bj = 1;
        while (bj < n){
            if(buckets[bi][2] < 1){
                bi++;
                bj++;
            }else {
                if(buckets[bj][2] < 1){
                    bj++;
                }else {
                    if( (buckets[bj][0] - buckets[bi][1]) > ans){
                        ans = (buckets[bj][0] - buckets[bi][1]);
                    }
                    bi = bj;
                    bj = bj+1;
                }
            }
        }
        System.out.println(ans);
    }

    // 算出桶号
    static int indexOfBuckets(int min, int max, int val, int span){
        int cha = val - min;
        int i = cha / span;
        return i;
    }

}
/*
4
9 3 1 10
6

4
5 5 5 5
0
*/