排序综合应用（区间、拓扑、自定义比较器）

区间问题：排序是前提

区间题的第一步几乎永远是按左端点排序，有时需要按右端点排序。

合并区间（LeetCode 56）

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // 按左端点升序
    List<int[]> result = new ArrayList<>();
    int[] cur = intervals[0];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= cur[1]) {
            // 有重叠，合并（取更大的右端点）
            cur[1] = Math.max(cur[1], intervals[i][1]);
        } else {
            result.add(cur);
            cur = intervals[i];
        }
    }
    result.add(cur);
    return result.toArray(new int[0][]);
}

关键：intervals[i][0] <= cur[1] 判断是否重叠，等于也算（共享端点）。

无重叠区间（LeetCode 435）—— 按右端点排序

移除最少区间使剩余不重叠 = 保留最多不重叠区间（贪心：每次选右端点最小的）：

int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);  // 按右端点升序（贪心关键）
    int count = 1, end = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {  // 不重叠，选这个
            count++;
            end = intervals[i][1];
        }
        // 重叠，跳过（它的右端点 >= 当前 end，贪心不选）
    }
    return intervals.length - count;
}

为什么按右端点：右端点越小，"留给后续区间的空间越大"——这是贪心正确性的核心。

用最少箭刺穿气球（LeetCode 452）

与「无重叠区间」同构，按右端点排序：

int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));  // 注意用 compare，防止溢出
    int arrows = 1, end = points[0][1];
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > end) {  // 注意：等于 end 仍可被当前箭射中
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
}

与上题区别：>= vs >，因为箭射在右端点处可以戳破恰好到达该端点的气球。

自定义比较器的陷阱

最大数（LeetCode 179）

判断 a 和 b 哪个应该排在前面，比较 ab 和 ba 的字典序：

String largestNumber(int[] nums) {
    String[] strs = Arrays.stream(nums)
        .mapToObj(String::valueOf)
        .toArray(String[]::new);
    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
    if (strs[0].equals("0")) return "0";  // 全零特判
    return String.join("", strs);
}

为什么正确：比较器满足全序关系（传递性、反对称性），Java 排序保证正确性。

⚠️ 自定义比较器的溢出陷阱

// 危险：当 a = Integer.MIN_VALUE, b = 1 时，a - b 会溢出
Arrays.sort(arr, (a, b) -> a - b);

// 安全：使用 Integer.compare 或 Long
Arrays.sort(arr, (a, b) -> Integer.compare(a, b));
Arrays.sort(arr, Comparator.comparingInt(x -> x));

桶排序应用

前 K 个高频元素（LeetCode 347）

频次最大为 n，开 n+1 个桶，把频次作为下标：

List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    // 桶：下标 i 存放频次为 i 的所有元素
    List<Integer>[] bucket = new List[nums.length + 1];
    for (int i = 0; i <= nums.length; i++) bucket[i] = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        bucket[e.getValue()].add(e.getKey());
    }

    List<Integer> result = new ArrayList<>();
    for (int i = nums.length; i >= 0 && result.size() < k; i--) {
        result.addAll(bucket[i]);
    }
    return result;
}

时间：O(n)，优于排序的 O(n log n)。

最大间距（LeetCode 164）

n 个元素，最大间距保证 ≥ ceil((max-min)/(n-1))，利用桶排序保证同一桶内不是答案：

int maximumGap(int[] nums) {
    if (nums.length < 2) return 0;
    int n = nums.length;
    int min = Arrays.stream(nums).min().getAsInt();
    int max = Arrays.stream(nums).max().getAsInt();
    if (min == max) return 0;

    int bucketSize = Math.max(1, (max - min) / (n - 1));  // 桶的大小
    int bucketCount = (max - min) / bucketSize + 1;

    int[] bucketMin = new int[bucketCount];
    int[] bucketMax = new int[bucketCount];
    Arrays.fill(bucketMin, Integer.MAX_VALUE);
    Arrays.fill(bucketMax, Integer.MIN_VALUE);

    for (int num : nums) {
        int idx = (num - min) / bucketSize;
        bucketMin[idx] = Math.min(bucketMin[idx], num);
        bucketMax[idx] = Math.max(bucketMax[idx], num);
    }

    // 最大间距只可能出现在相邻非空桶之间
    int maxGap = 0, prevMax = bucketMax[0];
    for (int i = 1; i < bucketCount; i++) {
        if (bucketMin[i] == Integer.MAX_VALUE) continue;  // 空桶
        maxGap = Math.max(maxGap, bucketMin[i] - prevMax);
        prevMax = bucketMax[i];
    }
    return maxGap;
}

排序 + 二分

会议室 II（LeetCode 253）—— 差分数组法

用排序 + 最小堆跟踪最早结束时间：

int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();  // 最小堆，存结束时间
    for (int[] interval : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll();  // 复用一个会议室
        }
        endTimes.offer(interval[1]);
    }
    return endTimes.size();
}

直觉：每次处理新会议时，如果最早结束的会议已经结束，就复用那个房间；否则新开一个。

排序题型识别小结