Medium

题目描述

在一个无限的 2D 平面上，你需要处理一系列查询。

给定一个正整数 k 和一个 2D 数组 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]
解释：
- 最初有 0 个障碍物。
- 查询 [1,2] 后，少于 2 个障碍物。
- 查询 [3,4] 后，距离分别为 3 和 7 的障碍物。
- 查询 [2,3] 后，距离分别为 3、5 和 7 的障碍物。
- 查询 [-3,0] 后，距离分别为 3、3、5 和 7 的障碍物。

示例 2：

输入：queries = [[5,5],[4,4],[3,3]], k = 1
输出：[10,8,6]
解释：
- 查询 [5,5] 后，有距离为 10 的障碍物。
- 查询 [4,4] 后，有距离为 8 和 10 的障碍物。
- 查询 [3,3] 后，有距离为 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

解题思路

这道题要求我们动态维护第 k 近的障碍物距离。关键思路是使用最大堆来维护当前最近的 k 个障碍物距离。

核心思想：

  1. 使用大小为 k 的最大堆，堆顶始终是这 k 个距离中的最大值
  2. 当堆的大小小于 k 时，直接添加新障碍物的距离
  3. 当堆的大小等于 k 时：
    • 如果新距离小于堆顶（当前第 k 近的距离），则移除堆顶并添加新距离
    • 否则忽略新距离，因为它不会影响第 k 近的结果

算法步骤：

  1. 对于每个查询，计算障碍物到原点的曼哈顿距离 |x| + |y|
  2. 维护一个最大堆，确保堆中始终保存最近的 k 个距离
  3. 如果堆中元素少于 k 个，返回 -1；否则返回堆顶元素

这种方法的优势是能够高效地维护动态的第 k 小值，避免了每次都要对所有距离排序的开销。

推荐解法： 使用最大堆的解法，时间复杂度最优。

代码实现

class Solution {
public:
    vector<int> resultsArray(vector<vector<int>>& queries, int k) {
        vector<int> results;
        priority_queue<int> maxHeap; // 最大堆
        
        for (auto& query : queries) {
            int distance = abs(query[0]) + abs(query[1]);
            
            if (maxHeap.size() < k) {
                maxHeap.push(distance);
            } else if (distance < maxHeap.top()) {
                maxHeap.pop();
                maxHeap.push(distance);
            }
            
            if (maxHeap.size() < k) {
                results.push_back(-1);
            } else {
                results.push_back(maxHeap.top());
            }
        }
        
        return results;
    }
};

class Solution:
    def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:
        import heapq
        results = []
        max_heap = []  # 使用负数模拟最大堆
        
        for x, y in queries:
            distance = abs(x) + abs(y)
            
            if len(max_heap) < k:
                heapq.heappush(max_heap, -distance)
            elif distance < -max_heap[0]:
                heapq.heappop(max_heap)
                heapq.heappush(max_heap, -distance)
            
            if len(max_heap) < k:
                results.append(-1)
            else:
                results.append(-max_heap[0])
        
        return results

public class Solution {
    public int[] ResultsArray(int[][] queries, int k) {
        var results = new List<int>();
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        
        foreach (var query in queries) {
            int distance = Math.Abs(query[0]) + Math.Abs(query[1]);
            
            if (maxHeap.Count < k) {
                maxHeap.Enqueue(distance, distance);
            } else if (distance < maxHeap.Peek()) {
                maxHeap.Dequeue();
                maxHeap.Enqueue(distance, distance);
            }
            
            if (maxHeap.Count < k) {
                results.Add(-1);
            } else {
                results.Add(maxHeap.Peek());
            }
        }
        
        return results.ToArray();
    }
}

var resultsArray = function(queries, k) {
    const maxHeap = [];
    const results = [];
    
    const insertMaxHeap = (val) => {
        maxHeap.push(val);
        let idx = maxHeap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (maxHeap[idx] <= maxHeap[parentIdx]) break;
            [maxHeap[idx], maxHeap[parentIdx]] = [maxHeap[parentIdx], maxHeap[idx]];
            idx = parentIdx;
        }
    };
    
    const removeMaxHeap = () => {
        if (maxHeap.length === 0) return null;
        if (maxHeap.length === 1) return maxHeap.pop();
        
        const max = maxHeap[0];
        maxHeap[0] = maxHeap.pop();
        let idx = 0;
        
        while (true) {
            const leftChild = 2 * idx + 1;
            const rightChild = 2 * idx + 2;
            let largest = idx;
            
            if (leftChild < maxHeap.length && maxHeap[leftChild] > maxHeap[largest]) {
                largest = leftChild;
            }
            if (rightChild < maxHeap.length && maxHeap[rightChild] > maxHeap[largest]) {
                largest = rightChild;
            }
            
            if (largest === idx) break;
            [maxHeap[idx], maxHeap[largest]] = [maxHeap[largest], maxHeap[idx]];
            idx = largest;
        }
        
        return max;
    };
    
    for (const [x, y] of queries) {
        const distance = Math.abs(x) + Math.abs(y);
        
        if (maxHeap.length < k) {
            insertMaxHeap(distance);
        } else if (distance < maxHeap[0]) {
            removeMaxHeap();
            insertMaxHeap(distance);
        }
        
        results.push(maxHeap.length === k ? maxHeap[0] : -1);
    }
    
    return results;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n log k)，其中 n 是查询次数，每次堆操作需要 O(log k) 时间
空间复杂度O(k)，最大堆最多存储 k 个元素

相关题目