题解 | #最小的K个数#

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //想到了主持人的那个问题，主持人题目要难一点，除了用最小堆，还要把活动时间进行排序
        //主持人用的是最小堆，默认的就行。它需要先对活动时间进行排序，依次安排最早的活动

        // 实现最大堆，默认的PriorityQueue实现的是最小堆，就是主持人那题用到的
        // 这里面需要实现最大堆，也就是堆顶存放的是最大值，之后把最大值挤掉，留下的就是小的，不用先对数组进行排序
        // 最大堆的实现需要重新定义compare方法
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a,Integer b){
                return b.compareTo(a);
            }
        });
        for (int i = 0; i < input.length; i++) {
            //把四个最大数字装入堆，然后依次把堆顶让出来
            pq.offer(input[i]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        //这样堆里面的k个数字就是最小的k个数字了，现在问题就是把堆转换为ArrayList即可
        ArrayList<Integer> res = new ArrayList<>(pq);
        return res;
    }

}

知识点： PriorityQueue 优先级队列，默认是最小堆，最大堆需要重新定义compare方法。

因为要留下最小的数字，把最大的数字依次挤走，所以可以确定本题使用最大堆。