java - 创建maxHeap，Collections.reverseOrder() 和((a, b) -> b - a) 的区别；

Question

我在一个 leetcode 问题中遇到了一个边缘案例，当我使用 new PriorityQueue<>(Collections.reverseOrder()); 时它通过了，但是当我使用 new PriorityQueue<>((a, b) -> b - a);解决方案未被接受。

leetcode题目是480. Sliding Window Median https://leetcode.com/problems/sliding-window-median/

代码如下:

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] res = new double[nums.length - k + 1];
        PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        // This doesn't work:
        //PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> right = new PriorityQueue<>();

        for (int i = 0; i < nums.length; i++) {
            if (left.size() <= right.size()) {
                right.add(nums[i]);
                left.add(right.remove());
            } else {
                left.add(nums[i]);
                right.add(left.remove());
            }
            if (left.size() + right.size() == k) {
                double median;
                if (left.size() == right.size()) {
                    median = (double)((long)left.peek() + (long)right.peek()) / 2;
                } else {
                    median = (double)left.peek();
                }
                int start = i - k + 1;
                res[start] = median;
                if (!left.remove(nums[start])) {
                    right.remove(nums[start]);
                }
            }
        }
        return res;

    }
}

我认为创建 maxHeap 的不同方法是相同的，我不知道为什么它会导致不同的结果，因为边缘情况很棘手。

Answer 1

b - a 可以上溢和下溢(假设 b 已经是 Integer.MIN_VALUE)。使用 Integer.compare(b, a)相反。