C++算法入门练习——数据流第K大元素
现有一个初始为空的序列S，对其执行n个操作，每个操作是以下两种操作之一：
- 往序列S中加入一个正整数x；
- 输出当前序列S中第k大的数。
其中，第k大是指将序列从大到小排序后的第k个数。
利用stl里的priority_queue自动实现最大堆排序。
这里用个小技巧，输入时，如果已经当前堆有了k个数，那么再输入一个数后，要弹出，这样就可以保持堆里只包含k个数，而堆顶的数就是第k大的数。
完整代码如下：
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
priority_queue<int,vector<int>,greater<int>> q;
int n,k;
cin>>n>>k;
string stemp;
int temp;
for(int i=0;i<n;i++){
cin>>stemp;
if(stemp=="Push"){
cin>>temp;
q.push(temp);
if(q.size()>k){
q.pop();
}
}
else{
if(q.size()>=k){
temp = q.top();
cout<<temp<<endl;
}
else{
cout<<"-1"<<endl;
}
}
}
return 0;
}