【Leetcode 每日一题】3066. 超过阈值的最少操作数 II

问题背景

给你一个下标从 0 0 0 开始的整数数组 n u m s nums nums 和一个整数 k k k。
一次操作中，你将执行：

1. 选择 n u m s nums nums 中最小的两个整数 x x x 和 y y y。
2. 将 x x x 和 y y y 从 n u m s nums nums 中删除。
3. 将 m i n ( x , y ) × 2 + m a x ( x , y ) min(x, y) \times 2 + max(x, y) min(x,y)×2+max(x,y) 添加到数组中的任意位置。

注意，只有当 n u m s nums nums 至少包含两个元素时，你才可以执行以上操作。
你需要使数组中的所有元素都大于或等于 k k k，请你返回需要的 最少 操作次数。

数据约束

• 2 ≤ n u m s . l e n g t h ≤ 2 × 1 0 5 2 \le nums.length \le 2 \times 10 ^ 5 2≤nums.length≤2×105
• 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \le nums[i] \le 10 ^ 9 1≤nums[i]≤109
• 1 ≤ k ≤ 1 0 9 1 \le k \le 10 ^ 9 1≤k≤109
• 输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k k k。

解题过程

始终要维护数组中的最小值，用堆很好处理。
用数组实现的手写堆，在平台上的表现比直接调用 API 会好不少。这里用到了之前说实现 堆排序 的过程中可以逃课的向上调整。还是没躲过，索性就记一下。

具体实现

调用优先队列 API

class Solution {
    public int minOperations(int[] nums, int k) {
        Queue<Long> heap = new PriorityQueue<>();
        for(int num : nums) {
            heap.offer((long) num);
        }
        int res = 0;
        while(heap.peek() < k) {
            long min1 = heap.poll();
            long min2 = heap.poll();
            heap.offer(2 * min1 + min2);
            res++;
        }
        return res;
    }
}

自己实现堆

class Solution {
    public int minOperations(int[] nums, int k) {
        int n = nums.length;
        long[] heap = new long[n];
        int size = 0;
        for(int num : nums) {
            heap[size++] = num;
        }
        buildHeap(heap, size);
        int res = 0;
        // 每次循环从最小堆的堆顶取出两个最小值，加入新元素并维护堆结构
        while(heap[0] < k) {
            long min1 = heap[0];
            swap(heap, 0, --size);
            downAdjust(heap, 0, size);
            long min2 = heap[0];
            swap(heap, 0, --size);
            downAdjust(heap, 0, size);
            heap[size++] = 2 * min1 + min2;
            upAdjust(heap, size - 1);
            res++;
        }
        return res;
    }

    // 交换数组中的两个元素
    private void swap(long[] heap, int i, int j) {
        long temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 从当前位置向上调整
    private void upAdjust(long[] heap, int cur) {
        while(heap[cur] < heap[(cur - 1) / 2]) {
            swap(heap, cur, (cur - 1) / 2);
            cur = (cur - 1) / 2;
        }
    }

    // 从当前位置向下调整
    private void downAdjust(long[] heap, int cur, int size) {
        int child = 2 * cur + 1;
        // 注意这里是子节点不超过数组范围
        while(child < size) {
            int target = child + 1 < size && heap[child + 1] < heap[child] ? child + 1 : child;
            target = heap[target] < heap[cur] ? target : cur;
            if(target == cur) {
                break;
            }
            swap(heap, cur, target);
            cur = target;
            child = 2 * cur + 1;
        }
    }

    // 自底向顶建堆
    private void buildHeap(long[] heap, int size) {
        for(int i = size; i >= 0; i--) {
            downAdjust(heap, i, size);
        }
    }
}