题解 | 相邻最大差值

class MaxDivision {
public:
    int findMaxDivision(vector<int>& A, int n) {
        if (n < 2) return 0;
        
        // 找出最大值和最小值
        int minVal = A[0], maxVal = A[0];
        for (int num : A) {
            minVal = min(minVal, num);
            maxVal = max(maxVal, num);
        }
        
        if (minVal == maxVal) return 0;
        
        // 创建n+1个桶
        vector<bool> used(n + 1, false);
        vector<int> minBucket(n + 1, INT_MAX);
        vector<int> maxBucket(n + 1, INT_MIN);
        
        // 计算桶大小
        double gap = double(maxVal - minVal) / n;
        
        // 将数字分配到桶中
        for (int num : A) {
            if (num == maxVal) continue;
            int idx = (num - minVal) / gap;
            used[idx] = true;
            minBucket[idx] = min(minBucket[idx], num);
            maxBucket[idx] = max(maxBucket[idx], num);
        }
        
        // 计算最大差值
        int maxGap = 0;
        int prev = minVal;
        for (int i = 0; i < n + 1; i++) {
            if (!used[i]) continue;
            maxGap = max(maxGap, minBucket[i] - prev);
            prev = maxBucket[i];
        }
        maxGap = max(maxGap, maxVal - prev);
        
        return maxGap;
    }
};

import java.util.*;

public class MaxDivision {
    public int findMaxDivision(int[] A, int n) {
        if (n < 2) return 0;
        
        // 找出最大值和最小值
        int minVal = A[0], maxVal = A[0];
        for (int num : A) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }
        
        if (minVal == maxVal) return 0;
        
        // 创建n+1个桶
        boolean[] used = new boolean[n + 1];
        int[] minBucket = new int[n + 1];
        int[] maxBucket = new int[n + 1];
        Arrays.fill(minBucket, Integer.MAX_VALUE);
        Arrays.fill(maxBucket, Integer.MIN_VALUE);
        
        // 计算桶大小
        double gap = (double)(maxVal - minVal) / n;
        
        // 将数字分配到桶中
        for (int num : A) {
            if (num == maxVal) continue;
            int idx = (int)((num - minVal) / gap);
            used[idx] = true;
            minBucket[idx] = Math.min(minBucket[idx], num);
            maxBucket[idx] = Math.max(maxBucket[idx], num);
        }
        
        // 计算最大差值
        int maxGap = 0;
        int prev = minVal;
        for (int i = 0; i < n + 1; i++) {
            if (!used[i]) continue;
            maxGap = Math.max(maxGap, minBucket[i] - prev);
            prev = maxBucket[i];
        }
        maxGap = Math.max(maxGap, maxVal - prev);
        
        return maxGap;
    }
}

class MaxDivision:
    def findMaxDivision(self, A, n):
        if n < 2:
            return 0
            
        min_val = max_val = A[0]
        for num in A:
            min_val = min(min_val, num)
            max_val = max(max_val, num)
            
        if min_val == max_val:
            return 0
            
        used = [False] * (n + 1)
        min_bucket = [float('inf')] * (n + 1)
        max_bucket = [-float('inf')] * (n + 1)
        
        gap = float(max_val - min_val) / n
        
        for num in A:
            if num == max_val:
                continue
            idx = int((num - min_val) / gap)
            used[idx] = True
            min_bucket[idx] = min(min_bucket[idx], num)
            max_bucket[idx] = max(max_bucket[idx], num)
            
        max_gap = 0
        prev = min_val
        for i in xrange(n + 1):
            if not used[i]:
                continue
            max_gap = max(max_gap, min_bucket[i] - prev)
            prev = max_bucket[i]
        max_gap = max(max_gap, max_val - prev)
        
        return max_gap