Skip to content

Latest commit

 

History

History
223 lines (171 loc) · 6.43 KB

README.md

File metadata and controls

223 lines (171 loc) · 6.43 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1419
第 413 场周赛 Q2
数组
堆（优先队列）

3275. 第 K 近障碍物查询

English Version

题目描述

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

给你一个正整数 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 * 105
  • 所有 queries[i] 互不相同。
  • -109 <= queries[i][0], queries[i][1] <= 109
  • 1 <= k <= 105

解法

方法一：优先队列（大根堆）

我们可以使用一个优先队列（大根堆）来维护离原点最近的 $k$ 个障碍物。

遍历 $\textit{queries}$，每次计算 $x$ 和 $y$ 的绝对值之和，然后将其加入优先队列。如果优先队列的大小超过 $k$，则弹出堆顶元素。如果当前优先队列的大小等于 $k$，则将堆顶元素加入答案数组，否则将 $-1$ 加入答案数组。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n \times \log k)$，空间复杂度 $O(k)$。其中 $n$ 为数组 $\textit{queries}$ 的长度。

Python3

class Solution:
    def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:
        ans = []
        pq = []
        for i, (x, y) in enumerate(queries):
            heappush(pq, -(abs(x) + abs(y)))
            if i >= k:
                heappop(pq)
            ans.append(-pq[0] if i >= k - 1 else -1)
        return ans

Java

class Solution {
    public int[] resultsArray(int[][] queries, int k) {
        int n = queries.length;
        int[] ans = new int[n];
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; ++i) {
            int x = Math.abs(queries[i][0]) + Math.abs(queries[i][1]);
            pq.offer(x);
            if (i >= k) {
                pq.poll();
            }
            ans[i] = i >= k - 1 ? pq.peek() : -1;
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> resultsArray(vector<vector<int>>& queries, int k) {
        vector<int> ans;
        priority_queue<int> pq;
        for (const auto& q : queries) {
            int x = abs(q[0]) + abs(q[1]);
            pq.push(x);
            if (pq.size() > k) {
                pq.pop();
            }
            ans.push_back(pq.size() == k ? pq.top() : -1);
        }
        return ans;
    }
};

Go

func resultsArray(queries [][]int, k int) (ans []int) {
	pq := &hp{}
	for _, q := range queries {
		x := abs(q[0]) + abs(q[1])
		pq.push(x)
		if pq.Len() > k {
			pq.pop()
		}
		if pq.Len() == k {
			ans = append(ans, pq.IntSlice[0])
		} else {
			ans = append(ans, -1)
		}
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

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 (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int   { return heap.Pop(h).(int) }

TypeScript

function resultsArray(queries: number[][], k: number): number[] {
    const pq = new MaxPriorityQueue();
    const ans: number[] = [];
    for (const [x, y] of queries) {
        pq.enqueue(Math.abs(x) + Math.abs(y));
        if (pq.size() > k) {
            pq.dequeue();
        }
        ans.push(pq.size() === k ? pq.front().element : -1);
    }
    return ans;
}