【Leetcode Daily】3275第K近障碍物查询

发表于2025-12-17|更新于2025-12-17|力扣日常 | LeetcodeDaily

|总字数:251|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个二维数组，每个其中的一维数组代表一个点，求从左向右遍历，已遍历点中距离原点第 k 近的那个距离（x 的绝对值加 y 的绝对值）

思路分享

与【Leetcode Daily】703数据流中的第K大元素十分相近，要注意的是，堆中能确定的就是堆顶，不要以为建了小顶堆后，这个堆的第 k 个就是第 k 小。但维护长度 k 的大顶堆一定满足这个条件。

https://leetcode.cn/problems/k-th-nearest-obstacle-queries/solutions/2900061/zui-da-dui-wei-hu-qian-k-xiao-pythonjava-h15x/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:
        rec = []
        ans = [-1] * len(queries)
        heapq.heapify(rec)
        for i, (x, y) in enumerate(queries):
            heapq.heappush(rec, -(abs(x)+abs(y)))
            if i < k-1:
                continue
            if len(rec) > k:
                heapq.heappop(rec)
            ans[i] = -rec[0]
        return ans

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/b546109d.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

相关推荐

【Leetcode Daily】2558从数量最多的堆取走礼物

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组，并重复 k 次找其中最大的数字平方再放回去，返回最后数组的数值和。思路分享对于这种找最大/最小的情况，可以考虑堆。堆会自然维护堆顶为所有元素的最小或者最大，并且在去除这个最值后，也能很方便地提取出下一个最值。那有人可能就问了，之前学的单调栈和单调队列不也能方便地取最值吗，为什么不用？原因是单调栈和单调队列的维护效率不及堆，在本题，提取的最值处理后又要放回去，提取是方便，但放回去的最坏情况是O(n)，即从最大值变最小值。 https://leetcode.cn/problems/take-gifts-from-the-richest-pile/solutions/2501655/yuan-di-dui-hua-o1-kong-jian-fu-ti-dan-p-fzdh/ 代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def pickGifts(self, gifts: List[int], k: int) ->...

【Leetcode Daily】295数据流的中位数

题目浅析想查看原题可以点击题目链接。简单地说，就是在给数组增添数字的过程中，可能需要随时输出当前的中位数。思路分享构建大小堆，也就是一个大顶堆和一个小顶堆，前者相当于当前数字的左侧，后者相当于右侧，这样就能随时得到左边最大和右边最小的数值，也就方便计算中位数了。 https://leetcode.cn/problems/find-median-from-data-stream/solutions/3015873/ru-he-zi-ran-yin-ru-da-xiao-dui-jian-ji-4v22k/ 具体而言，需要保证两点，第一是优先把数字放左侧，随后如果左侧的数字更多，再放右边；第二保证左侧的所有数字都小于右侧，所以如果要加到左侧的数字，可以先加到右侧，再从右侧获取最小的数字加到左侧。代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314151617181920212223class MedianFinder: def __init__(self): self.left = [] ...

【Leetcode Daily】480滑动窗口中位数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组和一个窗口大小 k，现在规定这个窗口从数组最左侧移到最右侧，求每个窗口的中位数。思路分享比起【Leetcode Daily】295数据流的中位数，本题多加了需要删除的功能，但是对于堆而言，想要找到其中的值再删除，相当于重建，复杂度比较高。这里就可以引入“懒删除堆”，顾名思义，这个堆删除值不会立刻删除，而是先记录下来，在做入堆，取堆顶等操作的同时，检查堆顶是否为需要删除的值，是则直接弹出堆顶，不是则照常操作。 https://leetcode.cn/problems/sliding-window-median/solutions/3628827/295-ti-lan-shan-chu-dui-pythonjavacgojsr-66ch/ 注意，对于大小堆这种写法引入删除后，注意保持 left 的 size 与 right 相等或者多...

【Leetcode Daily】1046最后一块石头的重量

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个一维数组，当作一堆石头重量，每次选两个最重的碰，将两个石头之差放回去，求最后剩下的一个石头重量（没有就0）思路分享这种多次求最值的，用堆，只是要记得，python的 heapify 默认最小堆，所以数字先做负数处理再堆化。 https://leetcode.cn/problems/last-stone-weight/solutions/540130/zui-hou-yi-kuai-shi-tou-de-zhong-liang-b-xgsx/ 代码解答（强烈建议自行解答后再看）参考题解 12345678910111213class Solution: def lastStoneWeight(self, stones: List[int]) -> int: for i in range(len(stones)): stones[i] = -stones[i] heapify(stones) while stones and...

【Leetcode Daily】3264K次乘运算后的最终数组I

题目浅析想查看原题可以点击题目链接。简单地说，就是给一维数组，k 和 m，k 次从数组中找到最小的值，原地乘 m，求最终的数组。思路分享本题比较重要的一点是，题目要求是在原地进行乘法操作，所以如果要用堆处理，需要同时保存下标信息。接下来就好说了，先做出保存下标信息的堆，然后不断取出小值乘 m 放回，直到达到 k 次。代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]: rec = [(x, i) for i, x in enumerate(nums)] heapify(rec) for _ in range(k): new_num = rec[0][0] * multiplier new_index = rec[0][1] ...

【Leetcode Daily】2336无限集中的最小数字

题目浅析想查看原题可以点击题目链接。简单地说，就是要实现一个数据结构，这个结构初始是一个正整数集合，要求能返回集合中的最小值，并随时往集合里加正整数。思路分享返回最小值，可以用堆来维护，至于堆是维护新加的，还是已有的，就看具体实现方式。但都需要思考如何去重，避免重复添加。官方题解提到了 SortedSet，可以在完成堆的任务的同时，高效去重。就不需要像参考题解这样，又用堆，也用 Set 了。 https://leetcode.cn/problems/smallest-number-in-infinite-set/solutions/2542156/wu-xian-ji-zhong-de-zui-xiao-shu-zi-by-l-5mfr/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718192021222324252627282930class SmallestInfiniteSet: def __init__(self): self.heap = [1] ...

数据加载中