What is the time complexity of solving Take Gifts From the Richest Pile?

The time complexity is O(n + k \times \log n) because we build the heap once (O(n)) and perform k heap operations (O(log n)) for each second.

What data structure is used to solve this problem?

A max-heap (priority queue) is used to efficiently track the richest pile during the simulation process.

How does GhostInterview help with heap-related problems?

GhostInterview provides practice and detailed explanations for heap-related problems, guiding you through essential operations like heapify and extraction.

How do I handle edge cases in this problem?

Edge cases can include piles with the same number of gifts, or very small values for k. GhostInterview provides feedback on handling these situations efficiently.

Can I modify the gift-taking process in Take Gifts From the Richest Pile?

Yes, you could modify the amount taken each second, such as taking a quarter or a third of the gifts instead of half. This variant changes the heap update strategy.

#2558

Easy

auto_awesome堆

LeetCode 题解工作台

从数量最多的堆取走礼物

给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：选择礼物数量最多的那一堆。如果不止一堆都符合礼物数量最多，从中选择任一堆即可。将堆中的礼物数量减少到堆中原来礼物数量的平方根，向下取整。返回在 k 秒后剩下的礼物数量。示例 1：输入： gifts = [2…

数组堆（优先队列）模拟

题目描述

给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：

选择礼物数量最多的那一堆。
如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
将堆中的礼物数量减少到堆中原来礼物数量的平方根，向下取整。

返回在 k 秒后剩下的礼物数量。

示例 1：

输入：gifts = [25,64,9,4,100], k = 4
输出：29
解释： 
按下述方式取走礼物：
- 在第一秒，选中最后一堆，剩下 10 个礼物。
- 接着第二秒选中第二堆礼物，剩下 8 个礼物。
- 然后选中第一堆礼物，剩下 5 个礼物。
- 最后，再次选中最后一堆礼物，剩下 3 个礼物。
最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。

示例 2：

输入：gifts = [1,1,1,1], k = 4
输出：4
解释：
在本例中，不管选中哪一堆礼物，都必须剩下 1 个礼物。 
也就是说，你无法获取任一堆中的礼物。 
所以，剩下礼物的总数量是 4 。

提示：

1 <= gifts.length <= 10³
1 <= gifts[i] <= 10⁹
1 <= k <= 10³

lightbulb

解题思路

方法一：优先队列（大根堆）

我们将数组 $gifts$ 转存到大根堆中，然后循环 $k$ 次，每次取出堆顶元素，将堆顶元素开根号的结果再放入堆中。

最后累加堆中所有元素之和作为答案。

时间复杂度 $O(n + k \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $gifts$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        h = [-v for v in gifts]
        heapify(h)
        for _ in range(k):
            heapreplace(h, -int(sqrt(-h[0])))
        return -sum(h)

speed

复杂度分析

指标	值
时间	O(n + k \times \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of heaps and their operations.
question_mark
The candidate can effectively simulate the problem using heap operations.
question_mark
The candidate handles edge cases, such as all piles having the same number of gifts.

warning

常见陷阱

外企场景

error
Not using a max-heap to efficiently access and update the richest pile.
error
Confusing the heap structure with a min-heap or failing to properly simulate the gift-taking process.
error
Incorrectly summing the remaining gifts at the end, missing the final result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if you are allowed to modify the gift-taking process, such as taking only a quarter or a third of the gifts instead of half?
arrow_right_alt
How would the problem change if the number of seconds were unlimited?
arrow_right_alt
What if we had multiple rounds of taking gifts and the number of seconds varied for each round?

help

常见问题

外企场景

继续练习

#2532 过桥的时间 #2593 标记所有元素后数组的分数 #2500 删除每行中的最大值