2558. 从数量最多的堆取走礼物

给你一个整数数组 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 <= 103
1 <= gifts[i] <= 109
1 <= k <= 103

思路

暴力法(5ms)
1. 每次找到最大礼物堆，计算出剩余的礼物数
2. 进过·k次后统计gifts之和
暴力法优化嵌套循环(4ms)
1. 同上，将每次找最大礼物堆单独独立成一个方法
使用PriorityQueue队列的特性(5ms)
使用最大堆来完成(最大堆是一种特殊的完全二叉树)(1ms)

代码

暴力法(5ms)

class Solution {
    public long pickGifts(int[] gifts, int k) {
        long sum = 0;
        while (k-- > 0) {
            int max = gifts[0];
            int index = 0;
            for (int i = 0; i < gifts.length; i++) {
                if (gifts[i] > max) {
                    max = gifts[i];
                    index = i;
                }
            }
            gifts[index] = (int) Math.sqrt(gifts[index]);
        }
        for (int gift : gifts) {
            sum += gift;
        }
        return sum;
    }
}

暴力法优化嵌套循环(4ms)

class Solution {
    public long pickGifts(int[] gifts, int k) {
        long sum = 0;
        while (k-- > 0) {
            int index = getMaxIndex(gifts);
            gifts[index] = (int) Math.sqrt(gifts[index]);
        }
        for (int gift : gifts) {
            sum += gift;
        }
        return sum;
    }

    private int getMaxIndex(int[] gifts) {
        int max = gifts[0];
        int index = 0;
        for (int i = 0; i < gifts.length; i++) {
            if (gifts[i] > max) {
                max = gifts[i];
                index = i;
            }
        }
        return index;
    }
}

使用PriorityQueue队列的特性(5ms)

class Solution {
    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int gift : gifts) {
            pq.offer(gift);
        }
        while (k > 0) {
            k--;
            int x = pq.poll();
            pq.offer((int) Math.sqrt(x));
        }
        long res = 0;
        while (!pq.isEmpty()) {
            res += pq.poll();
        }
        return res;
    }
}

使用最大堆来完成(最大堆是一种特殊的完全二叉树)(1ms)

class Solution {
    public long pickGifts(int[] gifts, int k) {
        int len = gifts.length;
        // 将数组构建成最大堆
        heapify(gifts, len);

        // 执行 k 次操作
        while (k > 0 && gifts[0] > 1) {
            k--;
            // 将堆顶元素（最大值）取平方根
            gifts[0] = (int) Math.sqrt(gifts[0]);
            // 对堆顶元素进行下沉操作，重新调整堆
            siftdown(gifts, 0, len - 1);
        }

        // 计算所有礼物的总和
        long res = 0;
        for (int i = 0; i < len; ++i) {
            res += gifts[i];
        }
        return res;
    }

    // 将数组构建成最大堆
    private void heapify(int[] nums, int len) {
        // 从最后一个非叶子节点开始，向前遍历
        for (int i = (len - 1) / 2; i >= 0; i--) {
            // 对每个节点进行下沉操作，构建最大堆
            siftdown(nums, i, len - 1);
        }
    }

    // 对节点 k 进行下沉操作
    private void siftdown(int[] nums, int k, int end) {
        // 当节点 k 有子节点时
        while (2 * k + 1 <= end) {
            // 左子节点的索引
            int j = 2 * k + 1;
            // 如果右子节点存在且比左子节点大，则选择右子节点
            if (j + 1 <= end && nums[j] < nums[j + 1]) {
                j++;
            }
            // 如果节点 k 的值小于子节点的值，则交换
            if (nums[k] < nums[j]) {
                swap(k, j, nums);
            } else {
                // 否则，堆已经调整完毕，退出循环
                break;
            }
            // 继续向下调整
            k = j;
        }
    }

    // 交换数组中的两个元素
    private void swap(int left, int right, int[] nums) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}