【Leetcode Daily】1942最小未被占据椅子的编号

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

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

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个数组，代表一群人到达和离开的时间，人一旦到达就会占据目前下标最小的座位，求名单第一个人占据到的座位下标。

思路分享

自己的思路与灵神有些相似，是用堆记录离开的时间对应座位下标，以及除默认最小下标座位外，因离开空出的座位，然后再按到达升序遍历人员，先释放应该离开的座位，然后让该人员入座，判断该人员是否名单第一位，是则返回结果。

https://leetcode.cn/problems/the-number-of-the-smallest-unoccupied-chair/solutions/894516/shi-jian-sao-miao-xian-dui-by-endlessche-5tzj/

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

参考题解

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        targetTime = times[targetFriend][0]
        min_seat = -1
        free_seat = []
        heapq.heapify(free_seat)
        seated = []
        heapq.heapify(seated)
        times.sort(key=lambda x : x[0])

        for time in times:
            while seated and seated[0][0] <= time[0]:
                free = heapq.heappop(seated)
                heapq.heappush(free_seat, free[1])
            
            if free_seat:
                nxt_seat = heapq.heappop(free_seat)
            else:
                min_seat += 1
                nxt_seat = min_seat

            if targetTime == time[0]:
                # print(targetTime)
                # print(time)
                # print(seated)
                # print(free_seat)
                return nxt_seat
            heapq.heappush(seated, (time[1], nxt_seat))

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/3edfc3cc.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] ...

数据加载中