Leetcode3275. 第 K 近障碍物查询

Every day a Leetcode

题目来源：3275. 第 K 近障碍物查询

解法1：大根堆

维护前 k 小元素，可以用最大堆。

遍历数组 queries，计算点 (x,y) 到原点的曼哈顿距离 d=∣x∣+∣y∣。

把 d 入堆，如果堆大小超过 k，就弹出堆顶（最大的元素）。

当堆的大小等于 k 时，堆顶就是第 k 小的距离。

代码：

/** @lc app=leetcode.cn id=3275 lang=cpp** [3275] 第 K 近障碍物查询*/// @lc code=start
class Solution
{
public:vector<int> resultsArray(vector<vector<int>> &queries, int k){int n = queries.size();vector<int> ans(n, -1);priority_queue<int> pq; // 大根堆for (int i = 0; i < n; i++){int dis = abs(queries[i][0]) + abs(queries[i][1]);pq.push(dis);if (pq.size() > k)pq.pop();if (pq.size() == k){// 堆顶就是当前第 k 小的距离ans[i] = pq.top();}}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(mlogk)，其中 m 是数组 queries 的长度。单次插入的时间复杂度是O(logk)。

空间复杂度：O(k)。返回值不计入。