本文共 2834 字，大约阅读时间需要 9 分钟。

?????????????????????????????????????????????????????????????????????????????????

????

????

import java.util.ArrayList;
class Tong {
    int max;
    int min;
    Tong() {
        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;
    }
}
public class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        int n = nums.length;
        int t = (max - min) / (n - 1);
        if (t == 0) {
            t = 1;
        }
        int sum = 1 + (max - min) / t;
        ArrayList
   
     tong = new ArrayList<>();
        for (int i = 0; i < sum; i++) {
            tong.add(new Tong());
        }
        for (int num : nums) {
            int x = (num - min) / t;
            if (x >= 0 && x < sum) {
                Tong bucket = tong.get(x);
                bucket.max = Math.max(bucket.max, num);
                bucket.min = Math.min(bucket.min, num);
            }
        }
        int maxGap = 0;
        int currentMin = Integer.MAX_VALUE;
        int currentMax = Integer.MIN_VALUE;
        for (int i = 0; i < sum; i++) {
            Tong bucket = tong.get(i);
            if (bucket.max == Integer.MIN_VALUE) {
                continue;
            }
            if (i == 0) {
                currentMin = bucket.min;
                currentMax = bucket.max;
            } else {
                if (currentMin == Integer.MAX_VALUE) {
                    currentMin = bucket.min;
                    currentMax = bucket.max;
                } else {
                    int gap = currentMax - currentMin;
                    if (gap > maxGap) {
                        maxGap = gap;
                    }
                    if (bucket.min < currentMin) {
                        currentMin = bucket.min;
                    }
                    if (bucket.max > currentMax) {
                        currentMax = bucket.max;
                    }
                }
            }
        }
        return maxGap;
    }
}
   

????

????????O(n)???????O(n)?????????????????????