原题地址（简单）

方法1—暴力

思路

我先想到的其实是优先队列，结果发现不太合适，就直接暴力了，因为我发现暴力的时间复杂度也不算太高，每次插入最大而已，所以就用暴力做了。

代码

class KthLargest {
public:
    vector<int> v;
    int K, n;
    KthLargest(int k, vector<int>& nums) {
        K = k;
        v = nums;
        n = v.size();
        if(n)   sort(v.begin(), v.end(), greater<int>());        
    }
    int add(int val) {
        v.push_back(val);
        n++;
        int i = n - 1, tmp = val;
        for(; i>=1; i--) {
            if(v[i-1] < tmp)  v[i] = v[i-1]; 
            else    break;
        }
        v[i] = tmp;
        return v[K-1];
    }
};
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

时空复杂度

时间复杂度 初始化排序时间复杂度为，插入的时间复杂度为
空间复杂度 存储数据嘛，为

方法2—优先队列

思路

优先队列就是堆嘛，每次只能取出一个最大值/最小值，所以要稍微转化一下思路。
用一个小顶堆来存储前K个数，堆顶的数不就是整个数组的第K大的数了嘛

代码

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> q;  // 存从大到小排列的前k个数
    int K;
    KthLargest(int k, vector<int>& nums) {
        K = k;
        for(auto num : nums)    q.push(num);
        int n = nums.size();
        for(int i=1; i<=n-K; i++)    q.pop();
    }
    int add(int val) {
        q.push(val);
        if(q.size() == K+1) q.pop();  // 加if是为了初始数组nums为空时也不出问题
        return q.top();
    }
};
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

时空复杂度

时间复杂度 初始化为，也就是建堆的时间复杂度，插入为
空间复杂度