数据流中的第 K 大元素(703)

703. 数据流中的第 K 大元素 - 力扣（LeetCode）

解答：

class KthLargest {
public:  //使用nums作为_q的底层存储，节省内存                                          KthLargest(int k, vector<int>& nums) : _k(k), _q(greater<int>(), move(nums)){while (_q.size() > k) {_q.pop();}}int add(int val){if (_q.size() == _k) {auto & i = _q.top();if (val > i) {_q.pop();_q.push(val);}} else {_q.push(val);}return _q.top();}private:int _k;priority_queue<int, vector<int>, greater<int>> _q;
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

总结：

计算复杂度add操作O(logN)，空间复杂度O(1)，维持一个最小堆，为了节省内存，可以使用nums作为底层存储。