【每日一题Day361】LC2558从数量最多的堆取走礼物 | 大顶堆
从数量最多的堆取走礼物【LC2558】
给你一个整数数组
gifts，表示各堆礼物的数量。每一秒，你需要执行以下操作：
- 选择礼物数量最多的那一堆。
- 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
- 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。
返回在
k秒后剩下的礼物数量*。*
-
思路
使用大顶堆存放所有礼物，每次将堆顶元素移出，并将其平方根放入堆中，最后求出堆中剩余礼物数目
-
实现
class Solution { public long pickGifts(int[] gifts, int k) { long res = 0L; PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1); for (int gift :gifts){ pq.add(gift); res += gift; } while(k-- > 0){ int poll = pq.poll(), left = (int)Math.sqrt(poll); res -= poll - left; pq.add(left); } return res; } }- 复杂度
- 时间复杂度： O ( n + k l o g n ) O(n+klogn) O(n+klogn)
- 空间复杂度： O ( n ) O(n) O(n)
- 复杂度