力扣3275题解：利用双堆结构高效处理查询问题

一、题目解读

力扣3275题要求我们处理一系列二维坐标查询，计算每个坐标到原点的曼哈顿距离，并动态维护前k小的距离。当查询数量达到k时，返回当前第k小的距离值；否则返回-1。这道题考查了数据结构的选择和动态数据处理能力。

二、解题思路

本解法采用双堆(大根堆+小根堆)的巧妙设计：

1. 大根堆(max_heap)存储当前前k-1小的元素

2. 小根堆(min_heap)存储剩余元素

3. 通过动态平衡两个堆的大小，确保大根堆顶部始终是第k小的元素

4. 每次查询都能在O(1)时间内获取结果

三、解题步骤

1. 初始化两个堆结构

2. 遍历每个查询，计算曼哈顿距离

3. 根据距离值决定插入哪个堆

4. 维护堆大小平衡：

• 当大根堆超过k个元素时，将顶部元素移到小根堆

• 当大根堆不足k个元素时，从小根堆取最小元素补充

5. 根据堆大小决定返回结果

四、完整代码实现

class Solution {
public:
    vector<int> resultsArray(vector<vector<int>>& queries, int k) {
        vector<int> results;
        priority_queue<int> max_heap; // 存前k-1小元素（大根堆）
        priority_queue<int, vector<int>, greater<int>> min_heap; // 存剩余元素
        
        for (const auto& q : queries) {
            int dist = abs(q[0]) + abs(q[1]);
            
            // 插入元素
            if (max_heap.empty() || dist <= max_heap.top()) {
                max_heap.push(dist);
            } else {
                min_heap.push(dist);
            }
            
            // 平衡堆大小
            if (max_heap.size() > k) {
                min_heap.push(max_heap.top());
                max_heap.pop();
            } else if (max_heap.size() < k && !min_heap.empty()) {
                max_heap.push(min_heap.top());
                min_heap.pop();
            }
            
            // 查询结果
            if (max_heap.size() >= k) {
                results.push_back(max_heap.top());
            } else {
                results.push_back(-1);
            }
        }
        return results;
    }
};

五、总结

这种双堆结构的时间复杂度为O(nlogk)，空间复杂度O(n)，非常适合处理动态数据流中的top-k问题。大根堆维护候选元素，小根堆作为辅助存储，通过精心设计的平衡策略，保证了算法的高效性。该解法不仅适用于本题，也可推广到类似的中位数、百分位数等统计问题。