有一个无限大的二维平面。给你一个正整数 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] 之后障碍物距离原点的距离分别为 335 和 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^55所有 queries[i] 互不相同。-109^99 queries[i][0], queries[i][1] 109^991 k 105^55我们可以用一个大小为k的大顶堆堆顶就是第k近障碍物classSolution{public:vectorintresultsArray(vectorvectorintqueries,intk){vectorintans;vectorinth;for(vectorintpoint:queries){intlenabs(point[0])abs(point[1]);if(h.size()k||h[0]len){h.push_back(len);push_heap(h.begin(),h.end());}if(h.size()k){pop_heap(h.begin(),h.end());h.pop_back();}if(h.size()k){ans.push_back(h[0]);}else{ans.push_back(-1);}}returnans;}};如果queries的大小为n则此算法时间复杂度为O(nlogk)空间复杂度为O(k)。
