【每日一题Day351】LC2530执行 K 次操作后的最大分数 | 原地堆化

class Solution {
    public long maxKelements(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);   
        long res = 0L;
        for (int num : nums){
            pq.add(num);
        }
        for (int i = 0; i < k; i++){
            int num = pq.poll();
            res += num;
            // pq.add(num / 3 + (num % 3 == 0 ? 0 : 1));
            pq.add((num + 2) / 3);
            pq.add((int)Math.ceil(num / 3.0));
        }
        return res;
    }
}

class Solution {
    public long maxKelements(int[] nums, int k) {
        heapify(nums); // 原地堆化（最大堆）
        long ans = 0;
        while (k-- > 0) {
            ans += nums[0]; // 堆顶
            nums[0] = (nums[0] + 2) / 3;
            sink(nums, 0); // 堆化（只需要把 nums[0] 下沉）
        }
        return ans;
    }
    // 原地堆化（最大堆）
    // 堆化可以保证 h[0] 是堆顶元素，且 h[i] >= max(h[2*i+1], h[2*i+2])
    private void heapify(int[] h) {
        // 下标 >= h.length / 2 的元素是二叉树的叶子，无需下沉
        // 倒着遍历，从而保证 i 的左右子树一定是堆，那么 sink(h, i) 就可以把左右子树合并成一个堆
        for (int i = h.length / 2 - 1; i >= 0; i--) {
            sink(h, i);
        }
    }
    // 把 h[i] 不断下沉，直到 i 的左右儿子都 <= h[i]
    private void sink(int[] h, int i) {
        int n = h.length;
        while (2 * i + 1 < n) {
            int j = 2 * i + 1; // i 的左儿子
            if (j + 1 < n && h[j + 1] > h[j]) { // i 的右儿子比 i 的左儿子大
                j++;
            }
            if (h[j] <= h[i]) { // 说明 i 的左右儿子都 <= h[i]，停止下沉
                break;
            }
            swap(h, i, j); // 下沉
            i = j;
        }
    }
    // 交换 h[i] 和 h[j]
    private void swap(int[] h, int i, int j) {
        int tmp = h[i];
        h[i] = h[j];
        h[j] = tmp;
    }
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/maximal-score-after-applying-k-operations/solutions/2487446/o1-kong-jian-zuo-fa-pythonjavacgojsrust-ztx6f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。