题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，并重复 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/

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

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        for i in range(len(gifts)):
            gifts[i] *= -1 # 默认是小顶堆，转化为大顶堆
        heapify(gifts)

        while k and -gifts[0] > 1:
            heapreplace(gifts, -isqrt(-gifts[0])) # 弹出堆中的最小项，同时推入“最大值”的平方
            k -= 1
        
        return -sum(gifts)