第 K 近障碍物查询

题目描述：

有一个无限大的二维平面。

给你一个正整数 k，同时给你一个二维数组 queries，包含一系列查询：

  • queries[i] = [x, y]：在平面上坐标 (x, y) 处建一个障碍物，数据保证之前的查询不会在这个坐标处建立任何障碍物。

每次查询后，你需要找到离原点第 k 近的障碍物到原点的距离。

请你返回一个整数数组 results，其中 results[i] 表示建立第 i 个障碍物以后，离原点第 k 近障碍物距离原点的距离。如果少于 k 个障碍物，results[i] == -1。

注意：一开始没有任何障碍物。

坐标在 (x, y) 处的点距离原点的距离定义为 |x| + |y|。

示例 1：

输入：queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2
输出：[-1,7,5,3]
解释：
最初，不存在障碍物。
queries[0] 之后，少于 2 个障碍物。
queries[1] 之后， 两个障碍物距离原点的距离分别为 3 和 7 。
queries[2] 之后，障碍物距离原点的距离分别为 3 ，5 和 7 。
queries[3] 之后，障碍物距离原点的距离分别为 3，3，5 和 7 。

示例 2：

输入：queries = [[5,5],[4,4],[3,3]], k = 1
输出：[10,8,6]
解释：
queries[0] 之后，只有一个障碍物，距离原点距离为 10 。
queries[1] 之后，障碍物距离原点距离分别为 8 和 10 。
queries[2] 之后，障碍物距离原点的距离分别为 6， 8 和 10 。

提示：

  • 1 <= queries.length <= 2 * 10^5
  • 所有 queries[i] 互不相同。
  • -10^9 <= queries[i][0], queries[i][1] <= 10^9
  • 1 <= k <= 10^5

解题思路

根据题目的要求，我们需要在遍历 queries 数组时，找到位于索引 i 处距离原点第 k 近的障碍物到原点的距离。为此，我们可以维护一个长度为 k 的有序数组，数组内的元素按照从小到大排列。为了高效地维护这个有序数组，我们可以使用 PriorityQueue（优先队列）作为数据结构。

相比于使用两个 stack（栈），其时间复杂度为 O(n)，在极端情况下，每次更新时都需要遍历整个 stack 的长度。而使用 PriorityQueue 的时间复杂度为 O(log(n))，每次维护队列的开销相对较小。因此，我们优先选择使用 PriorityQueue。

在遍历每个 i 时，我们对 PriorityQueue 进行维护，并且 PriorityQueue 的队顶元素就是该索引处的答案。这样可以高效地找到距离原点第 k 近的障碍物。

这一优化不仅简化了算法的复杂度，还确保了在大数据量的情况下，算法依然能高效地执行。

具体步骤如下：

  1. 距离计算： 每当在平面上新增一个障碍物时，计算该障碍物到原点的曼哈顿距离（|x| + |y|）。

  2. 最小堆维护： 使用一个最大堆（Max-Heap）来存储距离值，这样堆顶始终是当前 k 个距离中最大的那个。每当堆的大小小于 k 时，直接加入新的距离；如果堆的大小已经达到 k，并且新距离小于堆顶，则弹出堆顶并加入新的距离。

  3. 结果输出： 对于每个查询，如果堆的大小小于 k，表示还没有足够的障碍物，返回 -1；否则返回堆顶元素，即当前第 k 近的距离。

通过这种方法，我们可以保证每次查询时，都能在 O(log k) 的时间复杂度内完成堆的调整，从而高效地获取第 k 近的距离。

解题代码

 class Solution {
        public int[] resultsArray(int[][] queries, int k) {
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapComparator());
            int[] results = new int[queries.length];

            for (int i = 0; i < queries.length; i++) {
                int num = Math.abs(queries[i][0]) + Math.abs(queries[i][1]);
                add(maxHeap, num, k);
                results[i] = maxHeap.size() == k ? maxHeap.peek() : -1;
            }

            return results;
        }

        private void add(PriorityQueue<Integer> maxHeap, int num, int k) {
            if (maxHeap.size() < k) {
                maxHeap.add(num);
            } else if (num < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.add(num);
            }
        }

        public class MaxHeapComparator implements Comparator<Integer> {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }

        }
    }