从数量最多的堆取走礼物【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 )
