class Solution {
public:
vector<int> resultsArray(vector<vector<int>>& queries, int k) {
}
};
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 。
提示：
1 <= queries.length <= 2 * 105queries[i] 互不相同。-109 <= queries[i][0], queries[i][1] <= 1091 <= k <= 105相似题目
原站题解
cpp 解法, 执行用时: 654 ms, 内存消耗: 246.1 MB, 提交时间: 2024-10-18 09:11:33
class Solution {
public:
vector<int> resultsArray(vector<vector<int>>& queries, int k) {
vector<int> ans(queries.size(), -1);
priority_queue<int> pq;
for (int i = 0; i < queries.size(); i++) {
pq.push(abs(queries[i][0]) + abs(queries[i][1]));
if (pq.size() > k) {
pq.pop();
}
if (pq.size() == k) {
ans[i] = pq.top();
}
}
return ans;
}
};
java 解法, 执行用时: 93 ms, 内存消耗: 139.4 MB, 提交时间: 2024-10-18 09:10:28
class Solution {
public int[] resultsArray(int[][] queries, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
pq.offer(Math.abs(queries[i][0]) + Math.abs(queries[i][1]));
if (pq.size() > k) {
pq.poll();
}
ans[i] = pq.size() == k ? pq.peek() : -1;
}
return ans;
}
}
golang 解法, 执行用时: 484 ms, 内存消耗: 32.2 MB, 提交时间: 2024-10-18 09:10:06
func resultsArray(queries [][]int, k int) []int {
m := len(queries)
ans := make([]int, m)
if m < k {
for i := range ans {
ans[i] = -1
}
return ans
}
h := hp{make([]int, k)}
for i, q := range queries[:k] {
h.IntSlice[i] = abs(q[0]) + abs(q[1])
ans[i] = -1
}
heap.Init(&h)
ans[k-1] = h.IntSlice[0]
for i := k; i < m; i++ {
q := queries[i]
d := abs(q[0]) + abs(q[1])
if d < h.IntSlice[0] {
h.IntSlice[0] = d
heap.Fix(&h, 0)
}
ans[i] = h.IntSlice[0]
}
return ans
}
func resultsArray1(queries [][]int, k int) []int {
ans := make([]int, len(queries))
h := hp{}
for i, q := range queries {
heap.Push(&h, abs(q[0])+abs(q[1]))
if h.Len() > k {
heap.Pop(&h)
}
if h.Len() < k {
ans[i] = -1
} else {
ans[i] = h.IntSlice[0]
}
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func abs(x int) int { if x < 0 { return -x }; return x }
python3 解法, 执行用时: 409 ms, 内存消耗: 88.3 MB, 提交时间: 2024-10-18 09:09:10
# 最大堆
from heapq import heappush, heappop, heapreplace, heapify
class Solution:
def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:
ans = [-1] * len(queries)
h = []
for i, (x, y) in enumerate(queries):
heappush(h, -abs(x) - abs(y)) # 加负号变成最大堆
if len(h) > k:
heappop(h)
if len(h) == k:
ans[i] = -h[0]
return ans
# 优化
def resultsArray2(self, queries: List[List[int]], k: int) -> List[int]:
m = len(queries)
ans = [-1] * m
if m < k:
return ans
h = [-abs(x) - abs(y) for x, y in queries[:k]]
heapify(h)
ans[k - 1] = -h[0]
for i in range(k, m):
x, y = queries[i]
d = -abs(x) - abs(y)
if d > h[0]:
heapreplace(h, d)
ans[i] = -h[0]
return ans