力扣3275题解析：双堆优化动态维护曼哈顿距离的解题策略

一、题目解读

力扣3275题要求处理包含多个查询的二维数组，每个查询为坐标点，需实时计算各点到原点距离的前k小值，并返回对应结果数组。题目核心在于高效维护动态距离的有序性，考验对数据结构与算法优化的掌握。

二、解题思路

采用双堆优化策略：

1. 创建大根堆（max_heap）**存储前k-1小的距离，确保堆顶为当前第k大元素；

2. 创建小根堆（min_heap）**容纳剩余距离，维持堆顶为最小元素；

3. 通过比较新距离与max_heap顶值，动态分配元素至对应堆，并实时平衡堆大小；

4. 查询时直接取max_heap顶值，实现O(logk)的插入与查询效率。

三、解题步骤

1. 初始化：定义结果数组与双堆容器；

2. 循环处理查询：

    计算当前点曼哈顿距离（abs(x)+abs(y)）；

    若max_heap未满或距离更小，插入max_heap；否则入min_heap；

    若max_heap超k，将顶值移至min_heap；反之从min_heap补入max_heap；

    结果数组记录max_heap顶值或-1（若不足k）。

3. 返回结果数组。

四、代码与注释

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;  
    }  
};

注释解析：

● 双堆设计利用STL优先级队列，通过greater模板参数实现小根堆；

● 平衡逻辑确保max_heap始终为前k-1小值，min_heap容纳后续元素；

● 结果通过max_heap顶值动态更新，避免全排序开销。

五、总结

该解法巧妙结合双堆特性，将动态维护与分治思想融入曼哈顿距离问题，时间复杂度O(nlogk)，空间O(n)。核心在于利用堆结构快速定位临界值，降低全局排序成本。对处理实时有序数据的场景具有借鉴价值。