TopK

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

https://leetcode.cn/problems/kth-largest-element-in-a-stream/solutions/44721/703-shu-ju-liu-zhong-de-di-kda-yuan-su-liang-chong 思路一：multiset 利用 set 自动排序。

class KthLargest {
    int K;
    multiset<int> st;
public:
    KthLargest(int k, vector<int>& nums) {
        for (int n : nums) {
            st.insert(n);
            if (st.size() > k) st.erase(st.begin());
        }       
        K = k;

    }
    
    int add(int val) {
        st.insert(val);
        if (st.size() > K) st.erase(st.begin());
        return *st.begin();
    }
};

思路二：堆 priority_queue<Type, Container, Functional> Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。 如果不写后两个参数，那么容器默认用的是 vector，比较方式默认用 operator<，也就是优先队列是大顶堆，队头元素最大，本题为小顶堆。

class KthLargest {
    int K;
    priority_queue<int, vector<int>, greater<int>> pq;
public:
    KthLargest(int k, vector<int>& nums) {
        for (int n : nums) {
            pq.push(n);
            if (pq.size() > k) pq.pop();
        }
        K = k;
    }

    int add(int val) {
        pq.push(val);
        if (pq.size() > K) pq.pop();
        return pq.top();
    }
};