【数据结构-堆】力扣3275. 第 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 。

优先队列

class Solution {
public:
    vector<int> resultsArray(vector<vector<int>>& queries, int k) {
        int n = queries.size();
        vector<int> g;
        for(auto& query : queries){
            g.push_back(abs(query[0]) + abs(query[1]));
        }

        priority_queue<int> q;
        vector<int> results(n);
        for(int i = 0; i < n; i++){
            q.push(g[i]);
            if(q.size() > k){
                q.pop();
            }
            
            results[i] = q.size() < k ? -1 : q.top();
        }
        return results;
    }
};

这道题是找第k大的值，那么我们就可以构造一个大小为k的最小堆q，这时候q的队头元素就是第k大的元素。

我们先定义一个数组g来储存queries的距离，然后我们遍历i，建造障碍物实际上就是将g[i]推入到q中，这时候q会对内部元素进行升序排序，然后如果q大小大于k，那么队头元素被推出。这个时候q的队头元素则是第k近的障碍物，我们这时候记录到results中即可。