要求空间复杂度On，时间复杂度O(nlogk)。

一般我们说 topK 问题，就可以用大顶堆或小顶堆来实现
最大的 K 个：小顶堆
最小的 K 个：大顶堆

堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。
注意！大顶堆or小顶堆并非是从大到小的序列，因此才需要堆排序！ 堆可以分为大顶堆和小顶堆，大顶堆在内存中的一维存储（通常用数组或 std::vector 表示）满足以下性质：

堆顶元素（最大值）位于数组的第一个位置（arr[0]）。
对于任意节点arr[i]：
其左子节点为 arr[2*i + 1]。
其右子节点为 arr[2*i + 2]。
其父节点为 arr[(i-1)/2]（向下取整）。

堆的性质：
任意节点的值 ≥ 其子节点的值（大顶堆）。
大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

C++STL中的优先队列可以实现大根堆或小根堆，可以参考blog：
C++ | STL | 大顶堆 | 小顶堆 | std::priority_queue_c++ stl大顶堆-CSDN博客
大顶堆/小顶堆的构建以及排序的应用 – 知乎

//构造一个空的优先队列（此优先队列默认为大顶堆）
priority_queue<int> big_heap;   
//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int>> big_heap2;   
//构建小顶堆
priority_queue<int, vector<int>, greater<>> less_xheap;

因此本题求最小的k个数，可以维护一个大顶堆，当堆中的数目大于k，说明已经爆了，把堆顶的元素pop出去，最后留下来的k个一定是最小元素。

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
     std:: priority_queue<int> heap;

    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        // write code here
        if(k == 0) return{};
        if(input.size() <= k) return input;
        vector<int> res;
        for(auto& i : input){
            if(heap.size() <= k){
                heap.push(i);
            }
            if(heap.size() > k){
                heap.pop();
            }
        }
        while(!heap.empty()){
            res.emplace_back(heap.top());
            heap.pop();
        }
        return res;
    }
};