设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
示例:
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8
说明: 你可以假设 nums 的长度≥ k-1 且k ≥ 1。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
很经典的对顶堆题目，
考虑两个堆，左堆是大根堆，右堆是小根堆，维护左堆top < 右堆top左堆存储所有相对较小的n-K数，右堆存储相对较大的K个数插入值得时候先插入左堆，当左堆top > 右堆top时交换堆顶即可直接返回右堆堆顶就是k大值 #define debug #ifdef debug #include <time.h> #include "win_majiao.h" #endif #include <iostream> #include <algorithm> #include <vector> #include <string.h> #include <map> #include <set> #include <stack> #include <queue> #include <math.h> #define MAXN ((int)1e5+7) #define ll long long int #define INF (0x7f7f7f7f) #define fori(lef, rig) for(int i=lef; i<=rig; i++) #define forj(lef, rig) for(int j=lef; j<=rig; j++) #define fork(lef, rig) for(int k=lef; k<=rig; k++) #define QAQ (0) using namespace std; #define VVI vector<vector<int> > G #define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0) void err() { cout << "\033[39;0m" << endl; } template<typename T, typename... A> void err(T a, A... x) { cout << a << ' '; err(x...); } namespace FastIO{ char print_f[105]; void read() {} void print() { putchar('\n'); } template <typename T, typename... T2> inline void read(T &x, T2 &... oth) { x = 0; char ch = getchar(); ll f = 1; while (!isdigit(ch)) { if (ch == '-') f *= -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } x *= f; read(oth...); } template <typename T, typename... T2> inline void print(T x, T2... oth) { ll p3=-1; if(x<0) putchar('-'), x=-x; do{ print_f[++p3] = x%10 + 48; } while(x/=10); while(p3>=0) putchar(print_f[p3--]); putchar(' '); print(oth...); } } // namespace FastIO using FastIO::print; using FastIO::read; class KthLargest { public: int K; priority_queue<int> lef; priority_queue<int, vector<int>, greater<int> > rig; KthLargest(int k, vector<int>& nums) { this->K = k; for(auto x : nums) add(x); } int add(int val) { lef.push(val); while(rig.size()<K && !lef.empty()) { rig.push(lef.top()); lef.pop(); } while(!rig.empty() && !lef.empty() && lef.top()>rig.top()) { int x = lef.top(); lef.pop(); int y = rig.top(); rig.pop(); rig.push(x), lef.push(y); } return rig.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */ #ifdef debug signed main() { vector<int> vec = { 4, 5, 8, 2 }; KthLargest obj(3, vec); int ans = 0; ans = obj.add(3); cout << ans << endl; // returns 4 ans = obj.add(5); cout << ans << endl; // returns 5 ans = obj.add(10); cout << ans << endl; // returns 5 ans = obj.add(9); cout << ans << endl; // returns 8 ans = obj.add(4); cout << ans << endl; // returns 8 return 0; } #endif